最小边覆盖（最小路径覆盖）（路径不可相交）——pku2060

　路径覆盖就是在图中找一些路经，使之覆盖了图中的所有顶点，且任何一个顶点有且只有一条路径与之关联

最小路径覆盖就是找出最小的路径条数，使之成为Ｐ的一个路径覆盖．

最小路径覆盖=顶点数-最大匹配数（貌似与最大独立集同）

建图：集合A,B分别放顶点P,P'

如果出租车在X点可以Y点，则map[x][y]=1;//因为是X->Y,而题意Y显然无法到X,所以单向图

附上测试数据：

1

5

00:00 0 0 1 1

00:02 1 1 2 2

00:06 2 2 3 3

00:03 1 1 4 4

00:12 4 4 5 5

输出

2

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

struct data
{
    int time;
    int a,b,c,d;
}node[509];

int g,m;

bool map[509][509];
int mark[509];
bool flag[509];

bool dfs(int x)
{
    int i;
    for(i=1;i<=m;i++)
    {
        if(map[x][i]==0||flag[i]) continue;
        flag[i]=1;
        if(mark[i]==0||dfs(mark[i]))
        {
            mark[i]=x;
            return 1;
        }
    }
    return 0;
}

int dis(data x,data y)
{
    return abs(x.a-x.c)+abs(x.b-x.d)+abs(y.a-x.c)+abs(y.b-x.d);
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(mark,0,sizeof(mark));
        memset(map,0,sizeof(map));
        int n;
        scanf("%d",&n);
        g=m=n;
        int a,b;
        
        int i;
        for(i=1;i<=n;i++)
        {
            scanf("%d:%d",&a,&b);
            int time=a*60+b;
            
            node[i].time=time;
            scanf("%d%d%d%d",&node[i].a,&node[i].b,&node[i].c,&node[i].d);
        }
        
        int j;
        for(i=1;i<=n;i++)
        {
            for(j=i+1;j<=n;j++)
            {
                if(dis(node[i],node[j])<=node[j].time-node[i].time-1)
                {
                    map[i][j]=1;
                }
            }
        }

        int count=0;
        for(i=1;i<=g;i++)
        {
            memset(flag,0,sizeof(flag));
            if(dfs(i)) count++;
        }

        printf("%d\n",n-count);
    }
}