UVALive-3126 Taxi Cab Scheme （DAG的最小路径覆盖）

题目大意：要给n个人安排车，已知每个人的出发时间和起点与终点，问最少需要安排几辆车才能完成任务。

题目分析：最小路径覆盖。如果送完a到目的地后能在b出发之前赶来接b，那么连一条有向边a->b，最终将得到一个DAG。最少路径覆盖数便是答案。解法：把所有节点 i 拆成 i 和 i’，如果 i 和 j 之间连有一条边，那么则在二分图中连接 i->j’。最少路径覆盖数便是 n-最大匹配数。

代码如下：

# include<iostream>

# include<cstdio>

# include<vector>

# include<cstring>

# include<algorithm>

using namespace std;

# define REP(i,s,n) for(int i=s;i<n;++i)

# define CL(a,b) memset(a,b,sizeof(a))

# define CLL(a,b,n) fill(a,a+n,b)

const int N=505;

struct P

{

    int t,sx,sy,ex,ey;

};

P p[N];

int n,vis[N*2],link[N*2];

vector<int>G[N],G1[N*2];

bool ok(int i,int j)

{

    if(i==j) return false;

    int t=p[i].t+abs(p[i].ex-p[i].sx)+abs(p[i].ey-p[i].sy)+abs(p[i].ex-p[j].sx)+abs(p[i].ey-p[j].sy);

    return t+1<=p[j].t;

}

bool dfs(int x)

{

    REP(i,0,G1[x].size()){

        int y=G1[x][i];

        if(vis[y]) continue;

        vis[y]=1;

        if(link[y]==-1||dfs(link[y])){

            link[y]=x;

            return true;

        }

    }

    return false;

}

int match()

{

    CL(link,-1);

    int res=0;

    REP(i,1,2*n+1){

        CL(vis,0);

        if(dfs(i)) ++res;

    }

    return res;

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&n);

        REP(i,1,n+1){

            int a,b;

            scanf("%d",&a);

            getchar();

            scanf("%d",&b);

            p[i].t=a*60+b;

            scanf("%d%d%d%d",&p[i].sx,&p[i].sy,&p[i].ex,&p[i].ey);

        }

        REP(i,1,n+1) G[i].clear();

        REP(i,1,2*n+1) G1[i].clear();

        REP(i,1,n+1) REP(j,1,n+1) if(ok(i,j)) G[i].push_back(j);

        REP(i,1,n+1) REP(j,0,G[i].size()) G1[i*2-1].push_back(G[i][j]*2);

        int ans=match();

        printf("%d\n",n-ans);

    }

    return 0;

}