给你明天的出租车订单,订单中包含每个人的起点和终点坐标,还有时间,如果一辆出租车想接一个乘客必须在每个订单前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 - ans); } return 0; }