PKU2060 Taxi Cab Scheme - 最小路径覆盖

本文主要是介绍PKU2060 Taxi Cab Scheme - 最小路径覆盖，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：

出租车公司接到N（N<500）个订单，每个订单的描述是：t时刻需要从[x,y]坐标出发去[tx,ty]坐标。出租车行驶需要的时间是|x-tx|+|y-ty|。出租车公司希望派出最少的车完成所有的订单。派出一个出租车，它可以去接任何一个订单；若一个出租车在完成了一个订单之后，能在下一个订单的时刻之前赶到出发地点，那么它可以继续接下一个订单。输出最少需要多少出租车。

分析：

将一个订单作为有向无环图的一个节点，若订单i完成后能够赶到订单j，那么在有向图i到j之间连有向边。然后求这个有向图的最小路径覆盖。

最小路径覆盖问题可以转换为二分图最大匹配问题：若节点i到节点j有连边，那么在二部图的左边节点i到右边节点j连一条边。（事实上就是原来的有向图，只是转换为二分图来考虑）最小路径覆盖数=节点数N-最大匹配数。

关于这个题注意的是，不仅仅是前一个点的终点等于后一个点的起点才能连边，只要出租车在前一个目的地能开车赶到后一个起点也是可以连边的。

 /*
PKU2060 Taxi Cab Scheme
*/
#include <stdio.h> 
#include <memory.h> 
#define clr(a) memset(a,0,sizeof(a)) 
#define ABS(a) ((a)>0?(a):-(a)) 
#define N 1005 
typedef struct{
    int h,m;
}Time;
typedef struct{
    int x,y,tx,ty;
}Ride;
int find(int i,int m,int g[][N],int mat[],int tmat[]){
    int v,j;
    for(j=0;j<m;j++) if(g[i][j]&&tmat[j]==0){
        tmat[j]=1;v=mat[j];mat[j]=i;
        if(v==-1||find(v,m,g,mat,tmat)) return 1;
        mat[j]=v;
    }
    return 0;
}
int match(int g[][N],int n,int m,int mat[]){
    int i,j,v,k=0;
    int tmat[N];
    for(i=0;i<m;i++) mat[i]=-1;
    for(i=0;i<n;i++){clr(tmat); k+=find(i,m,g,mat,tmat);}
    return k;
}
//最小路径覆盖 
int PathCover(int g[][N],int n){
    int mat[N];
    return n-match(g,n,n,mat);
}
int Dist(int x,int y,int tx,int ty){
    return ABS(x-tx)+ABS(y-ty);
}
int Early(Time a,Ride p,Time b,Ride q){
    int dist=0;
    dist+=Dist(p.x,p.y,p.tx,p.ty);
    dist+=Dist(p.tx,p.ty,q.x,q.y);
    a.m+=dist;
    a.h+=a.m/60;
    a.m%=60;
    if(a.h<b.h) return 1;
    if(a.h>b.h) return 0;
    if(a.m<b.m) return 1;
    return 0;
}
Time t[N];
Ride r[N];
int a[N][N];
int main()
{
    int i,j,k;
    int T;
    int n;
    
    scanf("%d",&T);
    while(T--){
        //input 
        scanf("%d",&n);
        for(k=0;k<n;k++){
            scanf("%d:%d",&t[k].h,&t[k].m);
            scanf("%d%d%d%d",&r[k].x,&r[k].y,&r[k].tx,&r[k].ty);
        }
        //create map 
        clr(a);
        for(i=0;i<n;i++)
        for(j=i+1;j<n;j++)
            if( Early(t[i],r[i],t[j],r[j]) )
                a[i][j]=1;
        //output 
        printf("%d/n",PathCover(a,n));
    }
    return 0;
}
 