最小路径覆盖，在图上找尽量少的路径使得每个结点恰好在一条路径上(换句话说， 不同的路径不能有公共点)。单独的结点也看做一条路径。

[html]
/* **********************************************
Author : JayYe
Created Time: 2013-8-18 14:08:39
File Name : zzz.cpp
*********************************************** */

#include
#include
#include
using namespace std;

const int maxn = 500+10;

struct TAXI {
int time, x1, y1, x2, y2;
}a[maxn];

int n, match[maxn];
bool vis[maxn], mp[maxn][maxn];

bool dfs(int i) {
for(int j = 1;j <= n; j++) if(mp[i][j] && !vis[j]) {
vis[j] = 1;
if(!match[j] || dfs(match[j])) {
match[j] = i;
return true;
}
}
return false;
}

int main() {
int i, j, t;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
for(i = 1;i <= n; i++) {
int hour, minute;
scanf("%d:%d%d%d%d%d", &hour, &minute, &a[i].x1, &a[i].y1, &a[i].x2, &a[i].y2);
a[i].time = hour*60 + minute;
// 直接把时间全部转换成分钟，这样更好判断了。
}
for(i = 1;i <= n; i++) {
mp[i][i] = 0;
int time = a[i].time;
for(j = 1;j <= n; j++) if(j != i) {
int ti = time + abs(a[i].x1 - a[i].x2) + abs(a[i].y1 - a[i].y2);
ti += abs(a[i].x2 - a[j].x1) + abs(a[i].y2 - a[j].y1);
if(ti < a[j].time)
mp[i][j] = 1;
else
mp[i][j] = 0;
}
}

for(i = 1;i <= n; i++) match[i] = 0;
int ans = 0;
for(i = 1;i <= n; i++) {
for(j = 1;j <= n; j++) vis[j] = 0;
if(dfs(i)) ans++;
}
printf("%d\n", n - ans);
}
return 0;
}

/* **********************************************
Author : JayYe
Created Time: 2013-8-18 14:08:39
File Name : zzz.cpp
*********************************************** */

#include
#include
#include
using namespace std;

const int maxn = 500+10;

struct TAXI {
int time, x1, y1, x2, y2;
}a[maxn];

int n, match[maxn];
bool vis[maxn], mp[maxn][maxn];

bool dfs(int i) {
for(int j = 1;j <= n; j++) if(mp[i][j] && !vis[j]) {
vis[j] = 1;
if(!match[j] || dfs(match[j])) {
match[j] = i;
return true;
}
}
return false;
}

int main() {
int i, j, t;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
for(i = 1;i <= n; i++) {
int hour, minute;
scanf("%d:%d%d%d%d%d", &hour, &minute, &a[i].x1, &a[i].y1, &a[i].x2, &a[i].y2);
a[i].time = hour*60 + minute;
// 直接把时间全部转换成分钟，这样更好判断了。
}
for(i = 1;i <= n; i++) {
mp[i][i] = 0;
int time = a[i].time;
for(j = 1;j <= n; j++) if(j != i) {
int ti = time + abs(a[i].x1 - a[i].x2) + abs(a[i].y1 - a[i].y2);
ti += abs(a[i].x2 - a[j].x1) + abs(a[i].y2 - a[j].y1);
if(ti < a[j].time)
mp[i][j] = 1;
else
mp[i][j] = 0;
}
}

for(i = 1;i <= n; i++) match[i] = 0;
int ans = 0;
for(i = 1;i <= n; i++) {
for(j = 1;j <= n; j++) vis[j] = 0;
if(dfs(i)) ans++;
}
printf("%d\n", n - ans);
}
return 0;
}