poj 2060 Taxi Cab Scheme（DAG图的最小路径覆盖）

题意：

出租车公司有M个订单。

订单格式： hh:mm a b c d 　　　　含义：在hh:mm这个时刻客人将从（a,b）这个位置出发，他（她）要去（c,d）这个位置。

规定1：从（a,b）到（c,d）所花的时间为：abs(a-c)+abs(b-d)。

规定2：一辆出租车如果要接单，必须在客人出发前1分钟（包括）以前接单。

问，最少派出多少辆出租车，可以完成所有任务。

思路：

把每一笔单看成一个点，如果完成第i个单后可以接到第j个单，则 i->j连上线。

则题为：求这个DAG图的最小路径覆盖。

代码： *：记得要初始化！

struct node{

    int a,b,c,d,beginTime;

}ride[505];

int T,n;

char s[55];

vector<int> graph[505];

int cx[505],cy[505];

bool bmask[505];

int findPath(int u){

    int L=graph[u].size();

    rep(i,0,L-1){

        int v=graph[u][i];

        if(!bmask[v]){

            bmask[v]=true;

            if(cy[v]==-1||findPath(cy[v])){

                cy[v]=u;

                cx[u]=v;

                return 1;

            }

        }

    }

    return 0;

}

int MaxMatch(){

    int ans=0;

    rep(i,1,n) cx[i]=cy[i]=-1;

    rep(i,1,n) if(cx[i]==-1){

        mem(bmask,false);

        ans+=findPath(i);

    }

    return ans;

}

int ABS(int x,int y){

    return abs(x-y);

}

int main(){

    cin>>T;

    while(T--){

        scanf("%d",&n);

        rep(i,1,n) graph[i].clear();

        rep(i,1,n){

            int hour,minute;

            scanf("%d:%d",&hour,&minute);

            scanf("%d%d%d%d",&ride[i].a,&ride[i].b,&ride[i].c,&ride[i].d);

            ride[i].beginTime=60*hour+minute;

        }

        rep(i,1,n) rep(j,i+1,n){

            if(ride[i].beginTime+ABS(ride[i].a,ride[i].c)+ABS(ride[i].b,ride[i].d)+

               ABS(ride[i].c,ride[j].a)+ABS(ride[i].d,ride[j].b)+1<=ride[j].beginTime) graph[i].push_back(j);

        }

        int dd=MaxMatch();

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

    }

}

巴特西

poj 2060 Taxi Cab Scheme（DAG图的最小路径覆盖）

最新文章

热门文章