题目大意：
有n个出车安排，一辆车能接到这个安排的条件是：1、这辆车第一次发车；2、这辆车接了上一个安排，回到这个安排的起点的时间正好是这个安排的前一分钟或者更早
解题报告：
建图然后跑最小路径覆盖。就是答案。注意搭边的条件不是光看距离，还要加上每个任务的起点到终点的时间。
AC代码：（116ms）
#include<bits/stdc++.h> using namespace std; int n; int a,b; int line[1005][1005]; int nxt[1005]; bool used[1005]; struct Node { int x[3],y[3]; int time; int dis; } node[10005]; bool find(int x) { for(int i = 1; i<=n; i++) { if(line[x][i] == 1 && used[i] == 0) { used[i]=1; if(nxt[i] == 0 || find(nxt[i])) { nxt[i]=x; return 1; } } } return 0; } int main() { int t; cin>>t; while(t--) { scanf("%d",&n); memset(line,0,sizeof line); memset(nxt,0,sizeof nxt); for(int i = 1; i<=n; i++) { scanf("%d:%d %d %d %d %d",&a,&b,&node[i].x[0],&node[i].y[0],&node[i].x[1],&node[i].y[1]); node[i].time = a*60+b; node[i].dis = abs(node[i].x[0]-node[i].x[1]) + abs(node[i].y[0] - node[i].y[1]); } for(int i = 1; i<=n; i++) { for(int j = 1; j<=n; j++) {//或者j=i+1都可以ac if(node[i].dis + node[i].time + abs(node[j].x[0]-node[i].x[1]) + abs(node[j].y[0] - node[i].y[1]) < node[j].time) { line[i][j] = 1; } } } int ans = 0; for(int i = 1; i<=n; i++) { memset(used,0,sizeof used); if(find(i)) ans++; } printf("%d\n",n-ans); } return 0 ; }AC代码2：（26ms）
//邻接表会快多少？ #include <cstdio> #include <cstring> #include <algorithm> #include <cstdlib> #include <vector> using namespace std; const int N = 505; int t, n; struct People { int s, x1, y1, x2, y2; void read() { int h, m; scanf("%d:%d%d%d%d%d", &h, &m, &x1, &y1, &x2, &y2); s = h * 60 + m; } bool operator < (const People& c) const { return s < c.s; } } p[N]; vector<int> g[N]; bool judge(People a, People b) { int tmp = a.s + abs(a.x2 - a.x1) + abs(a.y2 - a.y1) + abs(a.x2 - b.x1) + abs(a.y2 - b.y1); if (tmp < b.s) return true; return false; } int match[N], vis[N]; bool dfs(int u) { for (int i = 0; i < g[u].size(); i++) { int v = g[u][i]; if (vis[v]) continue; vis[v] = 1; if (match[v] == -1 || dfs(match[v])) { match[v] = u; return true; } } return false; } int hungary() { int ans = 0; memset(match, -1, sizeof(match)); for (int i = 0; i < n; i++) { memset(vis, 0, sizeof(vis)); if (dfs(i)) ans++; } return ans; } int main() { scanf("%d", &t); while (t--) { scanf("%d", &n); for (int i = 0; i < n; i++) { g[i].clear(); p[i].read(); } sort(p, p + n); for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) { if (judge(p[i], p[j])) g[i].push_back(j); } printf("%d\n", n - hungary()); } return 0; }总结：
想想为什么 j=1或者j=i+1都可以AC？？？？
20190504：因为你sort了，，这样j=1~i这一部分都没必要遍历了，因为肯定不符合题意。
