题意：
出租车可以不停地做任务，任务是在一定时间内，把车从一个地方开到另一个地方。给出各项任务的具体时间和地点，问最少需要多少辆出租车来做任务？
分析:
首先，因为是在做二分匹配，所以肯定知道是用二分匹配做啦，如果是偶然遇到，真的不敢保证我能想到用二分匹配做；
既然用二分匹配做，那么首先就是构图啦，怎样建立匹配关系呢？就是在任务之间建立关系，把任何可能衔接在一起的任务当做一个匹配，那么很明显，接下来就是求这个图的一个最小路径覆盖了，求最小的路径覆盖所有的点，即完成所有的任务；
最小路径覆盖==点的个数-最大匹配
下面在计算时间的时候，将所有时间都转换成分了，这样少了很多判断了
#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
相关资源：数据结构—成绩单生成器