題意:
? ? ? 給你明天的出租車訂單,訂單中包含每個人的起點和終點坐標,還有時間,如果一輛出租車想接一個乘客必須在每個訂單前1分鐘到達,也就是小于等于time-1,問你完成所有訂單要最少多少量出租車...

思路:

? ? ?典型的最小路徑覆蓋,對于最小路徑覆蓋,我們可以這么理解,最次的情況是N輛,而只要找到那么一組可以與其匹配,就是用一輛車的就從n里減去一輛,我們找到最大的這種匹配數量,也就是最大匹配,然后N-ans ,就行了...這個題目有個地方挺坑的,就是給了個提示,說出租車可能跑到后半夜,一開始我sb了,當時間大于半夜凌晨就更新成第二天的時間,結果wa了,想想也是,更新完以前拉不了的活可能拉了,后來直接把更新的這個去掉就ac了,ac的時候感覺很奇怪,是不是數據弱? 我感覺可以不更新時間,而是把23.01 01.02 變成23.01 25.02,因為說了訂單是按時間順序給的,可是在仔細看看題目,說的是第二天的訂單,第二天是不是就不會出現第三天的任務? 如果會的話就會出現第四天的任務....fuck,不想了,就當他只有第二天的任務吧,所以無視那條提示就可以ac了.

#include<stdio.h> #include<string.h>#define N_node 500 + 50 #define N_edge 300000 typedef struct {int to ,next; }STAR;typedef struct {int t;int xs ,xe ,ys ,ye;int time; }NODE;STAR E[N_edge]; NODE node[N_node]; int list[N_node] ,tot; int mk_dfs[N_node] ,mk_gx[N_node];void add(int a ,int b) {E[++tot].to = b;E[tot].next = list[a];list[a] = tot; }int abss(int x) {return x > 0 ? x : -x; }int maxx(int x ,int y) {return x > y ? x : y; }bool ok(NODE a ,NODE b) {int dis = abss(a.xe - b.xs) + abss(a.ye - b.ys);int t = a.t + a.time + dis + 1;//if(t >= 1440) t -= 1440; return t <= b.t; }int Xyl_dfs(int s) {for(int k = list[s] ;k ;k = E[k].next){int to = E[k].to;if(mk_dfs[to]) continue;mk_dfs[to] = 1;if(mk_gx[to] == -1 || Xyl_dfs(mk_gx[to])){mk_gx[to] = s;return 1;}}return 0; }int main () {int t ,n ,i ,j; int h ,m;scanf("%d" ,&t);while(t--){scanf("%d" ,&n);for(i = 1 ;i <= n ;i ++){scanf("%d:%d %d %d %d %d" ,&h ,&m ,&node[i].xs ,&node[i].ys ,&node[i].xe ,&node[i].ye);node[i].t = h * 60 + m;node[i].time = abss(node[i].xs - node[i].xe) + abss(node[i].ys - node[i].ye);}memset(list ,0 ,sizeof(list));tot = 1;for(i = 1 ;i <= n ;i ++)for(j = i + 1 ;j <= n ;j ++){if(ok(node[i] ,node[j]))add(i ,j);}int ans = 0;memset(mk_gx ,255 ,sizeof(mk_gx));for(i = 1 ;i <= n ;i ++){memset(mk_dfs ,0 ,sizeof(mk_dfs));ans += Xyl_dfs(i);}printf("%d\n" ,n - ans);}return 0; }

總結

以上是生活随笔為你收集整理的hdu1960 最小路径覆盖的全部內容，希望文章能夠幫你解決所遇到的問題。

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