1350 Taxi Cab Scheme DAG最小路径覆盖

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

　　此题的题意：

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

　　思路：

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

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

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<queue>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 const int N=,INF=0x3f3f3f3f;

 int bmap[N][N],cx[N],cy[N],dx[N],dy[N];

 bool bmask[N];

 int nx,ny,dis,ans;

 bool searchpath()

 {

     queue<int> q;

     dis=INF;

     memset(dx,-,sizeof(dx));

     memset(dy,-,sizeof(dy));

     for(int i=;i<=nx;i++)

     {

         if(cx[i]==-){ q.push(i); dx[i]=; }

         while(!q.empty())

         {

             int u=q.front(); q.pop();

             if(dx[u]>dis) break;

             for(int v=;v<=ny;v++)

             {

                 if(bmap[u][v]&&dy[v]==-)

                 {

                     dy[v]= dx[u] + ;

                     if(cy[v]==-) dis=dy[v];

                     else

                     {

                         dx[cy[v]]= dy[v]+;

                         q.push(cy[v]);

                     }

                 }

             }

         }

     }

     return dis!=INF;

 }

 int findpath(int u)

 {

     for(int v=;v<=ny;v++)

     {

         if(!bmask[v]&&bmap[u][v]&&dy[v]==dx[u]+)

         {

             bmask[v]=;

             if(cy[v]!=-&&dy[v]==dis) continue;

             if(cy[v]==-||findpath(cy[v]))

             {

                 cy[v]=u; cx[u]=v;

                 return ;

             }

         }

     }

     return ;

 }

 void maxmatch()

 {

     ans=;

     memset(cx,-,sizeof(cx));

     memset(cy,-,sizeof(cy));

     while(searchpath())

     {

         memset(bmask,,sizeof(bmask));

         for(int i=;i<=nx;i++)

             if(cx[i]==-) ans+=findpath(i);

     }

 }

 void init()

 {

     memset(bmap,,sizeof(bmap));

 }

 struct node

 {

     int x,y,a,b,s,t;

 }e[N];

 int main()

 {

     //freopen("test.txt","r",stdin);

     int i,j,k,n,cas,s,t,a,b;

     scanf("%d",&cas);

     while(cas--)

     {

         scanf("%d",&n);

         init();

         for(i=;i<=n;i++){

             scanf("%d:%d",&a,&b);

             e[i].s=a*+b;

             scanf("%d%d%d%d",&e[i].x,&e[i].y,&e[i].a,&e[i].b);

             e[i].t= e[i].s+abs(e[i].a +-e[i].x)+abs(e[i].b-e[i].y);

         }

         for(i=;i<=n;i++){

             for(j=;j<=n;j++){

                 if(i==j) continue;

                 t=abs(e[j].x-e[i].a)+abs(e[j].y-e[i].b);

                 if(e[j].s>e[i].t+t) bmap[i][j]=;

                 t=abs(e[i].x-e[j].a)+abs(e[i].y-e[j].b);

                 if(e[i].s>e[j].t+t) bmap[j][i]=;

             }

         }

         nx=ny=n;

         maxmatch();

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

     }

     return ;

 }

巴特西

1350 Taxi Cab Scheme DAG最小路径覆盖

最新文章

热门文章