UVALive - 3126 Taxi Cab Scheme(最小路径覆盖-二分图最大匹配)

题目链接：点击查看

题目大意：有n个人要坐出租车，每个人上车的时间已知，规定出租车必须在每个人上车之前的一分钟之前到达这个人的位置，之后给出每个人的当前坐标以及需要达到的目的地坐标，行驶完该段路程的时间是两个坐标的曼哈顿距离，现在要求最少的出租车数量，以达到每个乘客的需求都可以得到完成，求出这个最小值

题目分析：很显然，当一个出租车送完一个乘客之后，肯定可以去接送其他乘客，根据送完乘客的位置和下一个乘客的起点来计算一下时间是否足够，若满足时间关系，则可以建边，接下来就是一个求最小路径覆盖的问题了，最小路径覆盖的定义：在一个有向图中，找出最少的路径，使得这些路径，经过每一个点，且每一个点只与一条路径相关联，然后跑一遍匈牙利就出来答案了，不过需要注意一下，这个时候求出的ans并不是最终答案，而是一共有几个客户可以乘坐之前客户用过的车，这样就不用提供新车了，所以答案是n-ans

需要注意的一点是，因为需要建立有向图，所以二重循环遍历的时候，第二重for的起点是i+1，而不是从1开始

代码：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=550;int n;int match[N];bool maze[N][N],vis[N]; struct Node {int t1,t2,x1,y1,x2,y2; }a[N];int dis(int x1,int y1,int x2,int y2) {return abs(x1-x2)+abs(y1-y2); }bool dfs(int x) {for(int i=1;i<=n;i++){if(maze[x][i]&&!vis[i]){vis[i]=true;if(!match[i]||dfs(match[i])){match[i]=x;return true;}}}return false; }void init() {memset(match,0,sizeof(match));memset(maze,false,sizeof(maze)); }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int w;cin>>w;while(w--){init();scanf("%d",&n);for(int i=1;i<=n;i++){int h,m;scanf("%d:%d%d%d%d%d",&h,&m,&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);a[i].t1=h*60+m;a[i].t2=a[i].t1+dis(a[i].x1,a[i].y1,a[i].x2,a[i].y2);}for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){if(a[i].t2+dis(a[i].x2,a[i].y2,a[j].x1,a[j].y1)<a[j].t1)maze[i][j]=true;}}int ans=0;for(int i=1;i<=n;i++){memset(vis,false,sizeof(vis));if(dfs(i))ans++;}printf("%d\n",n-ans);}return 0; }

 

总结

以上是生活随笔为你收集整理的UVALive - 3126 Taxi Cab Scheme(最小路径覆盖-二分图最大匹配)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。