題目鏈接：點擊查看

題目大意：有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(最小路径覆盖-二分图最大匹配)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。