1 /* 2 題意： 出租車 有一個出發的時間，從點（a, b）到點（c, d），時間為 3 abs(a-c)+abs(b-d)! 一輛車可以在運完一個乘客后運另一個乘客, 4 條件是此車要在預約開始前一分鐘之前到達出發地, 問最少需要幾輛車 5 搞定所有預約。 6 7 思路：有向邊進行建圖，因為出發時間是升序的！ 8 t0: (a0, b0) ->(c0, d0)表示預約在t0時間出發從(a,b)到(c,d);//節點x 9 t1: (a1, b1) ->(c1, d1)表示預約在t1時間出發從(a1,b1)到(c1,d1);//節點y 10 11 如果可能的話從t0時間出發的車到達目的地后，如果滿足從（c,d)到（a1,b1) 12 也就是從第一個目的地到達下一個出發地的時間t2 + 1<=t1, 那么完全就不用 13 其他的車再來了！兩次的預約都搞定了！ 14 如果滿足的話，節點x 和 節點y建立一條有向邊！ 15 最后通過匈牙利算法搞定..... 16 */ 17 #include<iostream> 18 #include<cmath> 19 #include<cstdio> 20 #include<cstring> 21 #include<algorithm> 22 #include<vector> 23 #define M 505 24 using namespace std; 25 26 struct point{ 27 int x, y; 28 point(){} 29 point(int x, int y){ 30 this->x=x; 31 this->y=y; 32 } 33 int operator -(point a) { 34 return abs(x-a.x) + abs(y-a.y); 35 } 36 }; 37 38 struct node{ 39 40 int begin, end; 41 point s, d; 42 }; 43 44 node nd[M]; 45 vector<int>v[M]; 46 int vis[M]; 47 int link[M]; 48 49 int n; 50 51 bool dfs(int cur){ 52 int len=v[cur].size(); 53 for(int i=0; i<len; ++i){ 54 int u=v[cur][i]; 55 if(vis[u]) continue; 56 vis[u]=1; 57 if(!link[u] || dfs(link[u])){ 58 link[u]=cur; 59 return true; 60 } 61 } 62 return false; 63 } 64 65 int main(){ 66 int t; 67 scanf("%d", &t); 68 while(t--){ 69 70 scanf("%d", &n); 71 for(int i=1; i<=n; ++i){ 72 int b, e, x1, y1, x2, y2; 73 scanf("%d:%d %d %d %d %d", &b, &e, &x1, &y1, &x2, &y2); 74 nd[i].begin=b*60+e; 75 nd[i].s=point(x1, y1); 76 nd[i].d=point(x2, y2); 77 nd[i].end=nd[i].begin+(nd[i].s-nd[i].d); 78 } 79 for(int i=1; i<n; ++i) 80 for(int j=i+1; j<=n; ++j){ 81 if(nd[j].begin>=nd[i].end+(nd[i].d-nd[j].s)+1)//如果能夠滿足條件愛你到達另一個出發地點，兩個節點之間建立一條有向邊 82 v[i].push_back(j); 83 } 84 int ans=0; 85 memset(link, 0, sizeof(link)); 86 for(int i=1; i<=n; ++i){ 87 memset(vis, 0, sizeof(vis)); 88 if(dfs(i)) ++ans; 89 } 90 cout<<n-ans<<endl; 91 for(int i=1; i<=n; ++i) 92 v[i].clear(); 93 } 94 return 0; 95 }
?
)
)
)
