首页 > 代码库 > poj 2060 Taxi Cab Scheme（DAG图的最小路径覆盖）
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图的最小路径覆盖）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。