出租车订单 / Taxi Cab Scheme

题目链接：ybt金牌导航3-1-3 / luogu UVA1201

题目大意

有 n 个人，有出发时间和出发到达位置，坐车是每分钟一个单位路程。
然后如果一个车可以在一个人出发前一分钟或更前时到达它的出发位置，那它就可以送这个人。
问你要每个人都坐车，最少要多少辆车。

思路

我们可以求出每两个人之间的这个关系：送完 $i$ 之后能不能送 $j$。

那如果我们将其反映为在图上 $i$ 连向 $j$，那就会出现一个 DAG，而一辆车可以解决一条链。

然后你就会发现它变成了最小路径覆盖问题。
由于如果 $i$ 到 $j$ 可以，$j$ 到 $k$ 可以，那根据题意看出 $i$ 到 $k$ 也可以，所以它已经是做完 Floyed 的状态，所以就可以直接跑不可相交的那个，直接上网络流。

代码

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#define INF 0x3f3f3f3f3f3f3f3f

using namespace std;

struct people {
	int a, b, c, d, ts, tt;
}a[501];
struct node {
	int x, to, nxt, op;
}e[600001];
int TI, n, x, y, le[2001], lee[2001], S, T, KK;
int dis[2001], ans;
queue <int> q;

void csh() {
	KK = 0;
	memset(le, 0, sizeof(le));
	
}

int get_num(int x, int op) {
	return op * n + x;
}

int abss(int x) {
	if (x < 0) return -x;
	return x;
}

bool ck(int x, int y) {
	int dis = abss(a[x].c - a[y].a) + abss(a[x].d - a[y].b);
	int times = a[y].ts - a[x].tt;
	if (times <= 0) return 0;
	return times >= dis + 1;//记得要快一分钟以上
}

//网络流dinic操作
void add(int x, int y, int z) {
	e[++KK] = (node){z, y, le[x], KK + 1}; le[x] = KK;
	e[++KK] = (node){0, x, le[y], KK - 1}; le[y] = KK;
}

bool bfs() {
	for (int i = 1; i <= T; i++) {
		dis[i] = -1;
		lee[i] = le[i];
	}
	while (!q.empty()) q.pop();
	
	dis[S] = 0;
	q.push(S);
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		
		for (int i = le[now]; i; i = e[i].nxt)
			if (e[i].x > 0 && dis[e[i].to] == -1) {
				dis[e[i].to] = dis[now] + 1;
				if (e[i].to == T) return 1;
				q.push(e[i].to);
			} 
	}
	
	return 0;
}

int dfs(int now, int sum) {
	if (now == T) return sum;
	
	int go = 0;
	for (int &i = lee[now]; i; i = e[i].nxt)
		if (dis[e[i].to] == dis[now] + 1 && e[i].x > 0) {
			int this_go = dfs(e[i].to, min(sum - go, e[i].x));
			if (this_go) {
				e[i].x -= this_go;
				e[e[i].op].x += this_go;
				go += this_go;
				if (go == sum) return go;
			}
		}
	
	return go;
}

void dinic() {
	while (bfs())
		ans -= dfs(S, INF);
}

int main() {
	scanf("%d", &TI);
	while (TI--) {
		csh();
		
		scanf("%d", &n);
		for (int i = 1; i <= n; i++) {
			scanf("%2d:%2d %d %d %d %d", &x, &y, &a[i].a, &a[i].b, &a[i].c, &a[i].d);
			a[i].ts = x * 60 + y;//出发的时间
			a[i].tt = a[i].ts + abss(a[i].a - a[i].c) + abss(a[i].b - a[i].d);//到达的时间
		}
		
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++) {
				if (i != j && ck(i, j)) {//能送完i之后去送j，连边ix->jy
					add(get_num(i, 0), get_num(j, 1), 1);
				}
			}
		
		S = 2 * n + 1;
		T = 2 * n + 2;
		for (int i = 1; i <= n; i++)
			add(S, i, 1);
		for (int i = n + 1; i <= 2 * n; i++)
			add(i, T, 1);
		
		ans = n;
		dinic();
		
		printf("%d\n", ans);
	}
	
	return 0;
}