1350 Taxi Cab Scheme DAG最小路径覆盖

　　对于什么是DAG最小路径覆盖以及解题方法在我的另外的博客已经有了。http://www.cnblogs.com/Potato-lover/p/3980470.html

　　此题的题意：

　　　　公交车（出租车）车站有一个固定的发车时间，有二维起点和终点，花费的时间是两点的曼哈顿距离，即|x1-x2| + |y1-y2| 。问最少需要多少辆车才能跑完所有路线。

　　思路：

　　　　A站点发车时间如果大于车到达B站点的时间与车从B站点到达A站点的时间，就可以连边。然后求最大匹配。最小路径覆盖 = 顶点数 - 最大匹配

　　　　有个小地方要注意，上面说的“大于”，那么等于可不可以呢？按样例2，等于是不可以的。　　

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<queue>
  5 #include<cmath>
  6 #include<algorithm>
  7 using namespace std;
  8 const int N=505,INF=0x3f3f3f3f;
  9 int bmap[N][N],cx[N],cy[N],dx[N],dy[N];
 10 bool bmask[N];
 11 int nx,ny,dis,ans;
 12 bool searchpath()
 13 {
 14     queue<int> q;
 15     dis=INF;
 16     memset(dx,-1,sizeof(dx));
 17     memset(dy,-1,sizeof(dy));
 18     for(int i=1;i<=nx;i++)
 19     {
 20         if(cx[i]==-1){ q.push(i); dx[i]=0; }
 21         while(!q.empty())
 22         {
 23             int u=q.front(); q.pop();
 24             if(dx[u]>dis) break;
 25             for(int v=1;v<=ny;v++)
 26             {
 27                 if(bmap[u][v]&&dy[v]==-1)
 28                 {
 29                     dy[v]= dx[u] + 1;
 30                     if(cy[v]==-1) dis=dy[v];
 31                     else
 32                     {
 33                         dx[cy[v]]= dy[v]+1;
 34                         q.push(cy[v]);
 35                     }
 36                 }
 37             }
 38         }
 39     }
 40     return dis!=INF;
 41 }
 42 int findpath(int u)
 43 {
 44     for(int v=1;v<=ny;v++)
 45     {
 46         if(!bmask[v]&&bmap[u][v]&&dy[v]==dx[u]+1)
 47         {
 48             bmask[v]=1;
 49             if(cy[v]!=-1&&dy[v]==dis) continue;
 50             if(cy[v]==-1||findpath(cy[v]))
 51             {
 52                 cy[v]=u; cx[u]=v;
 53                 return 1;
 54             }
 55         }
 56     }
 57     return 0;
 58 }
 59 void maxmatch()
 60 {
 61     ans=0;
 62     memset(cx,-1,sizeof(cx));
 63     memset(cy,-1,sizeof(cy));
 64     while(searchpath())
 65     {
 66         memset(bmask,0,sizeof(bmask));
 67         for(int i=1;i<=nx;i++)
 68             if(cx[i]==-1) ans+=findpath(i);
 69     }
 70 }
 71 void init()
 72 {
 73     memset(bmap,0,sizeof(bmap));
 74 }
 75 struct node
 76 {
 77     int x,y,a,b,s,t;
 78 }e[N];
 79 int main()
 80 {
 81     //freopen("test.txt","r",stdin);
 82     int i,j,k,n,cas,s,t,a,b;
 83     scanf("%d",&cas);
 84     while(cas--)
 85     {
 86         scanf("%d",&n);
 87         init();
 88         for(i=1;i<=n;i++){
 89             scanf("%d:%d",&a,&b);
 90             e[i].s=a*60+b;
 91             scanf("%d%d%d%d",&e[i].x,&e[i].y,&e[i].a,&e[i].b);
 92             e[i].t= e[i].s+abs(e[i].a +-e[i].x)+abs(e[i].b-e[i].y);
 93         }
 94         for(i=1;i<=n;i++){
 95             for(j=1;j<=n;j++){
 96                 if(i==j) continue;
 97                 t=abs(e[j].x-e[i].a)+abs(e[j].y-e[i].b);
 98                 if(e[j].s>e[i].t+t) bmap[i][j]=1;
 99                 t=abs(e[i].x-e[j].a)+abs(e[i].y-e[j].b);
100                 if(e[i].s>e[j].t+t) bmap[j][i]=1;
101             }
102         }
103         nx=ny=n;
104         maxmatch();
105         printf("%d
",n-ans);
106     }
107     return 0;
108 }

View Code