pku2060Taxi Cab Scheme

it2022-05-06  13

题意:

出租车可以不停地做任务,任务是在一定时间内,把车从一个地方开到另一个地方。给出各项任务的具体时间和地点,问最少需要多少辆出租车来做任务?

分析:

首先,因为是在做二分匹配,所以肯定知道是用二分匹配做啦,如果是偶然遇到,真的不敢保证我能想到用二分匹配做;

既然用二分匹配做,那么首先就是构图啦,怎样建立匹配关系呢?就是在任务之间建立关系,把任何可能衔接在一起的任务当做一个匹配,那么很明显,接下来就是求这个图的一个最小路径覆盖了,求最小的路径覆盖所有的点,即完成所有的任务;

最小路径覆盖==点的个数-最大匹配

下面在计算时间的时候,将所有时间都转换成分了,这样少了很多判断了

#include<iostream> #include<math.h> using namespace std; bool map[501][501],vis[501]; int match[501],n; struct road { int m; int ei,ej; }r[501]; int path(int s) { for(int i=1;i<=n;i++) if(map[s][i]&&!vis[i]) { vis[i]=1; if(match[i]==-1||path(match[i])) { match[i]=s; return 1; } } return 0; } int Max_Match() { memset(match,-1,sizeof(match)); int ans=0; for(int i=1;i<=n;i++) { memset(vis,0,sizeof(vis)); ans+=path(i); } return ans; } int main() { int cas,a,b,c,d,h1,m1,temp; scanf("%d",&cas); while(cas--) { scanf("%d",&n); memset(map,0,sizeof(map)); for(int i=1;i<=n;i++) { scanf("%d:%d %d %d %d %d",&h1,&m1,&a,&b,&c,&d); r[i].ei=c;r[i].ej=d; temp=abs(c-a)+abs(b-d); r[i].m=temp+m1+h1*60; for(int j=1;j<i;j++) { temp=abs(a-r[j].ei)+abs(b-r[j].ej); if(r[j].m+temp<m1+h1*60) map[i][j]=1; } } printf("%d\n",n-Max_Match()); } return 0; }

我始终不知道为什么下面这个比我快那么多

pku2060加快版 #include<iostream>using namespace std;struct Time{int h, m;};struct Task{int sx, sy, ex, ey; Time st;};Task v[505];char mat[505][505];int mx[505], my[505];char vstd[505];int nv;bool Early(Task a, Task b){int t = abs(a.ex-b.sx) + abs(a.ey-b.sy); t += abs(a.sx-a.ex) + abs(a.sy-a.ey); a.st.m += t; a.st.h += a.st.m/60; a.st.m %= 60;if(a.st.h < b.st.h) {return true; }else if(a.st.h == b.st.h) {if(a.st.m < b.st.m)return true; }return false;}int path(int s){int e;for(e = 1; e <= nv; e++) {if(mat[s][e] && !vstd[e]) { vstd[e] = 1;if(my[e]==-1 || path(my[e])) { my[e] = s; mx[s] = e;return 1; } } }return 0;}int MaxMatch(){int res = 0; memset(mx, -1, sizeof(mx)); memset(my, -1, sizeof(my));for(int i = 1; i <= nv; i++) {if(mx[i]==-1) { memset(vstd, 0, sizeof(vstd)); res += path(i); } }return res;}int main(){int cas;int i, j; scanf("%d", &cas);while(cas--) { scanf("%d", &nv);for(i = 1; i <= nv; i++) { scanf("%d:%d", &v[i].st.h, &v[i].st.m); scanf("%d %d %d %d", &v[i].sx, &v[i].sy, &v[i].ex, &v[i].ey); } memset(mat, 0, sizeof(mat));for(i = 1; i <= nv; i++) {for(j = 1; j <= nv; j++) {if(i==j) continue;if(Early(v[i],v[j])) { mat[i][j] = 1; } } }int res = nv - MaxMatch(); printf("%d\n", res); }return 0;}

转载于:https://www.cnblogs.com/nanke/archive/2011/08/29/2158965.html

相关资源:数据结构—成绩单生成器

最新回复(0)