题目大意：

有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这一部分都没必要遍历了，因为肯定不符合题意。