题解 【P4452 [国家集训队]航班安排】

传送门

虽然这题是个套路的费用流，但是作为刚学网络流的蒟蒻还是想了挺久。

一开始我是想的将一个点按照时刻拆成 $T$ 个点，然而先不说能不能做，就这个点数也能直接爆炸。

但是注意到请求数很少，把请求看做边会发现做不出来而且也是不合理的，于是考虑把每个请求看作一个点，点权为 $c_i$。因为网络流只能在边上搞事情，所以拆一下点。

接下来就是连边操作。首先建立超级源 $s$ 和超级汇 $t$，如果能够在 $s_i$ 时刻前从起点到达 $a_i$ 就连一条从 $s$ 到这个请求的边，容量 $1\sim \infty$ 之间都可以，费用是 $f[1][a_i]$

同理，如果能在 $T$ 时刻前回到起点就从这个请求连一条到 $t$ 的，容量在 $1\sim \infty$ 之间随便取，费用为 $f[b_i][1]$ 的边。

对于两个请求之间的转移，如果能在处理完 $u$ 请求后紧接着处理 $v$ 请求，连一条 $u\rightarrow v$，流量 $1\sim \infty$ 中随便取，费用为 $f[b_u][a_v]$ 的边。

对这个图直接跑一边最小费用最大流，把最小费用取个相反数就是答案。

为什么一定要最大流才是最优解呢？在条件允许的情况下，正常人都会多派几架飞机出去，哪怕不会让答案更优对不对。。。

#include <cstdio>
#include <queue>
#include <cstring>
#include <cstdlib>

inline int min(const int x, const int y) {return x < y ? x : y;}
const int INF = 1e9;
struct Node {int x, y;};
struct Edge {
	int to, nxt, cap, cost;
} e[100005];
int head[505], dis[505], cur[505], f[205][205], tme[205][205], tot = 1, s, t;
int a[205], b[205], S[205], T[205], c[205];
bool mark[505], vis[505];
std::queue<int> Q;
inline void AddEdge(const int u, const int v, const int cap, const int cost) {
	e[++ tot].to = v, e[tot].nxt = head[u], head[u] = tot;
	e[tot].cap = cap, e[tot].cost = cost;
	e[++ tot].to = u, e[tot].nxt = head[v], head[v] = tot;
	e[tot].cap = 0, e[tot].cost = -cost;
}

bool SPFA() {
	memset(vis, 0, sizeof vis);
	memset(dis, 0x3f, sizeof dis);
	memset(mark, 0, sizeof mark);
	memcpy(cur, head, sizeof cur);
	dis[s] = 0;
	Q.push(s);
	while (Q.size()) {
		int u(Q.front());
		Q.pop();
		mark[u] = false;
		for (int i(head[u]); i; i = e[i].nxt) {
			int v(e[i].to);
			if (e[i].cap && dis[u] + e[i].cost < dis[v]) {
				dis[v] = dis[u] + e[i].cost;
				if (!mark[v]) Q.push(v), mark[v] = true;
			}
		}
	}
	return dis[t] < INF;
}

int dfs(const int u, const int flow) {
	if (u == t) return flow;
	vis[u] = true;
	int tmp(0), used(0);
	for (int i(cur[u]); i; i = e[i].nxt) {
		cur[u] = i;
		if (e[i].cap && dis[u] + e[i].cost == dis[e[i].to] && !vis[e[i].to]) {
			int v(e[i].to);
			if (tmp = dfs(v, min(flow - used, e[i].cap))) {
				e[i].cap -= tmp, e[i ^ 1].cap += tmp, used += tmp;
				if (used == flow) return used;
			}
		}
	}
	if (!used) dis[u] = 0;
	return used;
}

int Dinic() {
	int Mincost(0);
	while (SPFA()) Mincost += dis[t] * dfs(s, INF);
	return Mincost;
}

int main() {
	int n, m, k, ed;
	scanf("%d%d%d%d", &n, &m, &k, &ed);
	for (int i(1); i <= n; ++ i)
	for (int j(1); j <= n; ++ j) scanf("%d", &tme[i][j]);
	for (int i(1); i <= n; ++ i)
	for (int j(1); j <= n; ++ j) scanf("%d", &f[i][j]);
	for (int i(1); i <= m; ++ i)
		scanf("%d%d%d%d%d", a + i, b + i, S + i, T + i, c + i), ++ a[i], ++ b[i];
	s = 0, t = 2 * m + 2;
	for (int i(1); i <= m; ++ i) {
		AddEdge(i + 1, i + m + 1, 1, -c[i]);
		if (tme[1][a[i]] <= S[i]) AddEdge(1, i + 1, 1, f[1][a[i]]);
		if (T[i] + tme[b[i]][1] <= ed) AddEdge(i + 1 + m, t, 1, f[b[i]][1]);
		for (int j(1); j <= m; ++ j)
			if (i != j && T[i] + tme[b[i]][a[j]] <= S[j])
				AddEdge(i + m + 1, j + 1, 1, f[b[i]][a[j]]);
	}
	AddEdge(0, 1, k, 0);
	printf("%d", -Dinic());
	return 0;
}