poj2060 Taxi Cab Scheme 最小路径覆盖=顶点数-最大匹配数

题意，租车，有n个预约，然后给出时间，然后给出地点，地点在一个二维坐标平面内，会给你两个坐标，求所需车最少数量；

分析：

这道题目跟poj2594一样穿了个马甲，2594是需要用一个floyd来转化，这里呢，根据坐标可以算出路径长度从而得到所需时间，如果本次预约任务结束时还有另一个预约时间还没到的话，那么这辆出租车可以接着去跑另一个任务，这样建图时就可以把两个预约连在一起，

讲的可能不是很清楚 但是一看代码 肯定好懂的

#include<iostream>#include<cstdio>#include<list>#include<algorithm>#include<cstring>#include<string>#include<queue>#include<stack>#include<map>#include<vector>#include<cmath>#include<memory.h>#include<set>#define ll long long#define LL __int64#define eps 1e-8const ll INF=9999999999999;using namespace std;#define M 400000100#define inf 0xfffffff//vector<pair<int,int> > G;//typedef pair<int,int> P;//vector<pair<int,int>> ::iterator iter;////map<ll,int>mp;//map<ll,int>::iterator p;vector<int>G[1212];char tempmp[1212];int mp[1212][1212];int marry[1212];bool vis[1212];int dis[2][4]={0,-1,0,1,1,0,-1,0};int n,m;struct Node{int a,b,c,d;int s,e;}node[1212];void clear(){memset(node,0,sizeof(node));memset(marry,-1,sizeof(marry));memset(mp,0,sizeof(mp));/*for(int i=0;i<1012;i++)G[i].clear();*/}int getstarttime(char *s)//获得该预约的开始时间{return ((s[0]-'0')*10+s[1]-'0')*60+(s[3]-'0')*10+s[4]-'0';}int getlasttime(int a,int b,int c,int d)//跑这个预约所持续 也就是所需要的时间{int t1,t2;t1=a-c;if(t1<0) t1=-t1;t2=b-d;if(t2<0) t2=-t2;return t1+t2;}bool dfs(int x){for(int i=1;i<=n;i++){if(mp[x][i] && !vis[i]){vis[i]=true;if(marry[i]==-1 || dfs(marry[i])){marry[i]=x;return 1;}}}return 0;}int main(void){int t;cin>>t;while(t--){clear();cin>>n;int a,b,c,d;for(int i=1;i<=n;i++){cin>>tempmp>>a>>b>>c>>d;int time=getstarttime(tempmp);node[i].s=time;//获取这个预约要开始的时间node[i].e=time+getlasttime(a,b,c,d);//获得跑完这个预约的时间node[i].a=a;node[i].b=b;node[i].c=c;node[i].d=d;}for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)if(node[i].e+getlasttime(node[i].c,node[i].d,node[j].a,node[j].b)<node[j].s) //如果跑完i预约时j预约的时间还未到，那么跑完i预约的车可以继续跑j这个预约mp[i][j]=1;//建图很简单int ans=0;for(int i=1;i<=n;i++)//接下来就是万能的模版了，{memset(vis,false,sizeof(vis));if(dfs(i))ans++;}cout<<n-ans<<endl;//最小路径覆盖=顶点数-最大匹配数}}

这道题目跟poj2594一样穿了个马甲，2594是需要用一个floyd来转化，这里呢，