pku2060 Taxi Cab Scheme

最小路径覆盖问题：用尽量少的不相交简单路径覆盖有向无环图的所有顶点。

由此满足条件：

１.一个单独的顶点是一条路径；

２．如果存在一路径p1,p2,......pk，其中p1 为起点，pk为终点，那么在覆盖图中，顶点p1,p2,......pk不再与其它的顶点之间存在有向边．

#include<stdio.h>
#include<math.h>

const int Maxn=501;
bool g[Maxn][Maxn],visit[Maxn];
int link[Maxn];
int n;
struct node //将每个出租情况抽象成有向无环图中的一个顶点

{
    int hour,minute,x1,x2,y1,y2;
    bool onTime(node var)    
    {
        if((var.hour-hour)*60+var.minute-minute>abs(x2-x1)+abs(y2-y1)+abs(var.x1-x2)+abs(var.y1-y2))
            return true;        //两点之间能构成有向边    

        else
            return false;
    }
}time[Maxn];

bool find(int x)
{
    for(int i=1;i<=n;i++)
    {
        if(g[x][i]&&!visit[i])
        {
            visit[i]=true;
            if(link[i]==0||find(link[i]))
            {
                link[i]=x;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    int cases;
    scanf("%d",&cases);
    while(cases--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                g[i][j]=false;
        for(int i=1;i<=n;i++)
            link[i]=0;
        for(int i=1;i<=n;i++)    
        {
            scanf("%d:%d%d%d%d%d",&time[i].hour,&time[i].minute,&time[i].x1,&time[i].y1,&time[i].x2,&time[i].y2);
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(time[i].onTime(time[j]))
                    g[i][j]=true;
        int match=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
                visit[j]=false;
            if(find(i))
                match++;
        }
        printf("%d\n",n-match);
    }
    return 0;
}