HDU_1960
如果把每条路线看成一个点,然后如果在任务i完成之后可以赶去做任务j就连一条i->j的有向边,这样我们就得到了一个有向无环图,而题目相当于想用最少的路径覆盖玩所有的顶点,这样就把问题转化成了二分图最小路径覆盖问题。
#include<stdio.h> #include<string.h> #include<stdlib.h> #define MAXD 510 #define MAXM 250010 char b[10]; int N, first[MAXD], e, next[MAXM], v[MAXM]; int yM[MAXD], visy[MAXD]; struct Task { int t, x1, y1, x2, y2; }task[MAXD]; int can(int i, int j) { return task[i].t + abs(task[j]. x1 - task[i].x2) + abs(task[j].y1 - task[i].y2) + abs(task[i].x2 - task[i].x1) + abs(task[i].y2 - task[i].y1) < task[j].t; } void add(int x, int y) { v[e] = y; next[e] = first[x], first[x] = e ++; } void init() { int i, j, hh, mm; scanf("%d", &N); for(i = 0; i < N; i ++) { scanf("%s%d%d%d%d", b, &task[i].x1, &task[i].y1, &task[i].x2, &task[i].y2); sscanf(b, "%d:%d", &hh, &mm); task[i].t = hh * 60 + mm; } memset(first, -1, sizeof(first[0]) * N), e = 0; for(i = 0; i < N; i ++) for(j = 0; j < N; j ++) if(can(i, j)) add(i, j); } int searchpath(int cur) { int i; for(i = first[cur]; i != -1; i = next[i]) if(!visy[v[i]]) { visy[v[i]] = 1; if(yM[v[i]] == -1 || searchpath(yM[v[i]])) { yM[v[i]] = cur; return 1; } } return 0; } void solve() { int i, ans = 0; memset(yM, -1, sizeof(yM[0]) * N); for(i = 0; i < N; i ++) { memset(visy, 0, sizeof(visy[0]) * N); if(searchpath(i)) ++ ans; } printf("%d\n", N - ans); } int main() { int t; scanf("%d", &t); while(t --) { init(); solve(); } return 0; }