网络流
一些概念
网络是指一个有向图 \(G = (V, E)\)，其中有一个源点 \(s\)，和一个汇点 \(t\)。同时我们定义 \(E\) 中的每条边 \((u, v)\) 都有容量 \(c(u, v)\) 和流量 \(f(u, v)\)。
其中流函数需要满足容量限制、斜对称、流量守恒，即：
- \(f(u, v) \leq c(u, v)\)
- \(f(u, v) = -f(v, u)\)
- \(\forall u \ne s, u \ne t, \sum_{(v, u) \in E} f(v, u) = \sum_{(u, v) \in E} f(u, v)\)
我们定义 \(u\) 的净流量为 \(f(u) = \sum_{(v, u) \in E} f(v, u) - \sum_{(u, v) \in E} f(u, v)\)，对于网络 \(G = (V, E)\) 和其上的流 \(f\)，我们定义 \(f\) 的流量 \(|f|\) 为 \(s\) 的净流量 \(f(s)\)。
容易发现根据流量守恒，\(f(s) = -f(t)\)，且 \(\forall u \in V, u \ne s, u\ne t, f(u) = 0\)。
同时我们定义剩余容量 \(c_f(u, v) = c(u, v) - f(u, v)\)。在任意时刻，网络中的所有节点以及剩余容量大于 \(0\) 的边构成的子图被称为残量网络。
对于网络 \(G = (V, E)\)，如果 \(\{S, T\}\) 满足 \(S \cup T = V\) 且 \(S \cap T = \varnothing\)，且 \(s \in S, t \in T\)，即 \(\{S, T\}\) 是 \(V\) 的一个划分，则 \(\{S, T\}\) 是 \(G\) 的一个 \(s-t\) 割。我们定义该割的容量为 \(||S,T|| = \sum_{u \in S}\sum_{u \in T}c(u, v)\)。你可以形象化的将割理解为一个边集 \(E' \in E\)，且 \(E'\) 被删去后网络的源点和汇点不再连通。
最大流
概念
顾名思义，令 \(G = (V, E)\)，则我们需要找到 \(G\) 上合适的流 \(f\)，使得整个网络的流量 \(|f|\) 最大化，流 \(f\) 就是最大流。
为了方便下文叙述，我们定义网络上的增广路指一条从 \(s\) 到 \(t\) 的各条边的剩余容量都大于 \(0\) 的路径。
Edmonds-Karp 增广路
EK 算法的思路是每次不断地用 BFS 找到增广路，直到网络上不存在增广路为止。
在每轮寻找增广路的过程中，EK 算法只考虑途中剩余容量大于 \(0\) 的边，用 BFS 找到一条从 \(s\) 到 \(t\) 包含边数最少的路径，同时计算出路径上各边剩余容量的最小值 \(incf\)，则网络的流量就可以增加 \(incf\)。
同时，当一条边 \((u, v)\) 的流量 \(f(u, v) > 0\) 时，根据斜对称性质，它的反向边流量 \(f(v, u) < 0\)，此时必有 \(f(v, u) < c(v, u)\)。于是就出现了一个很反直觉的事情是一条边的流量可能是负的。但事实上，在增广的过程中真正有意义的是剩余容量，所以我们可以将反向边流量的减小视为反向边剩余容量的增加——这意味着我们接下来可以通过走反向边来达成一种“反悔”的效果，和原先正向的增广抵消。
如下图（来自OI-wiki）：
所以我们在 EK 算法中只需要对于每条边记录它的剩余容量 \(c-f\) 即可。当一条边 \((u, v)\) 流过大小为 \(e\) 的流时，令 \(c_f(x, y)\) 减少 \(e\)，\(c_f(y, x)\) 增加 \(e\)。
再具体实现中有一个有用的技巧是将正反向边成对存储为 \(0,1;2,3;...\)，这样每次就可以通过边的编号异或 \(1\)，得到正反向边的编号。
EK 算法的上界时间复杂度为 \(O(|V||E|^2)\)，在实际中一般够不到上界，可以处理 \(10^3\sim 10^4\) 规模的网络。代码在后面费用流的时候会顺便给出，因为我从来没有单独写过 EK。
Dinic 算法
我们考虑 EK 算法比较慢的原因是它每次遍历残量网络时只找出一条增广路，就显得很不聪明，于是我们考虑进一步优化 EK。
我们考虑每次对网络流 BFS 建出分层图，然后在分层图上 DFS 寻找增广路，在回溯时更新剩余容量，每个点可以流向多条出边。
我们先给出代码再讲解其中的一些剪枝优化。（例题是 P3376 【模板】网络最大流）
const int N = 210, M = 10010;
int n, m, s, t;
int h[N], e[M], ne[M], now[N], idx;
LL w[M], d[N], maxflow, flow;
queue<int> q;
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
bool bfs() {
memset(d, 0, sizeof d);
while (!q.empty()) q.pop();
d[s] = 1; q.push(s); now[s] = h[s];
while (q.size()) {
int u = q.front(); q.pop();
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (w[i] && !d[v]) {
d[v] = d[u] + 1, now[v] = h[v];
q.push(v);
if (v == t) return true;
}
}
}
return false;
}
LL dinic(int u, LL flow) {
if (u == t) return flow; // 剪枝1
LL rest = flow, k;
for (int i = now[u]; ~i && rest; i = ne[i]) {
now[u] = i; int v = e[i]; // 剪枝3
if (w[i] && d[v] == d[u] + 1) {
k = dinic(v, min(rest, w[i]));
if (!k) d[v] = 0; // 剪枝2
rest -= k, w[i] -= k, w[i ^ 1] += k;
}
}
return flow - rest;
}
int main() {
n = read(), m = read(), s = read(), t = read();
memset(h, -1, sizeof h);
rep(i, 1, m) {
int a = read(), b = read(), c = read();
add(a, b, c); add(b, a, 0);
}
while (bfs())
while (flow = dinic(s, 1e10)) maxflow += flow;
printf("%lld\n", maxflow);
return 0;
}
剪枝 \(1\) 和 \(2\) 都比较简单，如果到达汇点就可以直接返回流量，如果当前某个节点不能对最大流产生任何贡献我们就不要再做它了。
剪枝 \(3\) 也被称为当前弧优化，它的目的是解决菊花图（即一个点 \(u\) 同时又大量入边和出边），如果每次 \(u\) 接受来自入边的流量后都遍历出边表则 \(u\) 这个局部最多可以达到 \(O(|E|^2)\) 的复杂度。所以如果某一个时候我们知道 \((u, v)\) 已经增广到了极限（无剩余容量或已经增广到堵车），就可以直接不考虑 \((u, v)\) 这条边，体现在邻接表中就是当前弧优化。
Dinic 的时间复杂度上界是 \(O(|V|^2|E|)\) 的，一般能够处理 \(10^4 \sim 10^5\) 规模的网络。
最大流和二分图匹配问题
二分图匹配问题实际上能够转化为最大流问题。
首先是二分图最大匹配问题，我们可以在原有二分图的基础上，让源点和二分图的左部点连边，让右部点和汇点连边，然后网络流中的所有边的容量都为 \(1\)。这样最大流就是二分图的最大匹配数。
其次是二分图的多重匹配，要求每个左部点只能连不超过 \(kl_i\) 条边，每个右部点只能连不超过 \(kr_i\) 条边。
解决这个问题，我们只需要在上述做法中所有源点向左部点 \(i\) 的连边的最大容量设为 \(kl_i\)；右部点 \(j\) 向汇点的连边的容量设为 \(kr_i\)。这样就可以直接跑最大流了
二分图最大匹配的可行边和必须边
给定一张二分图，若任何一个最大匹配方案都要包含边 \((u, v)\)，那么称 \((u, v)\) 为二分图最大匹配的必须边。类似地我们还可以定义二分图最大匹配的可行边和不可行边。
我们先考虑一个简化的情况————二分图的最大匹配是完备匹配。
根据定义，边 \((u, v)\) 是必须边的条件是：
- \((u, v)\) 为可行边
- 删除边 \((u, v)\) 后不能找到从 \(u\to v\) 的增广路
边 \((u, v)\) 是可行边的条件为：
- \((u, v)\) 当前为匹配边
- \((u, v)\) 当前为非匹配边，但对于当前 \(u\) 连接的点 \(x\) 和 \(v\) 连接的点 \(y\)，可以找到从 \(x\) 到 \(y\) 的一条增广路，这样 \(u\) 和 \(v\) 就可以相连了。
处理这种关系的一种方法是，把二分图 \(G = (V, E)\) 中的 “非匹配边” \((u, v)\) 在图 \(G'\) 上从 \(u\) 到 \(v\) 连边，对于匹配边 \((u, v)\) 则从 \(v\) 到 \(u\) 连边。
则 \(G\) 中从 \(u\) 到 \(v\) 有增广路（注意这里的增广路指的是二分图中的增广路而不是网络流中的增广路）相当于在 \(G'\) 中有从 \(u\) 到 \(v\) 的路径。
此时必须边的判定可以改写为从 \((u, v)\) 是当前二分图 \(G\) 的匹配边，并且 \(u, v\) 两点在有向图 \(G'\) 中属于不同的强连通分量。
原因是如果两个点在有向图 \(G'\) 中处于相同的强连通分量则在删除边 \((u, v)\) 后仍然能通过强连通分量中的点从 \(u\) 走到 \(v\)，就不符合先前必须边的条件。
类似地，可行边的条件是：\((u, v)\) 是当前二分图 \(G\) 的匹配边，或者 \(u\) 和 \(v\) 两点在有向图 \(G'\) 中存在于同一个强连通分量中。
当然，上述的都是完备匹配的情况。如果匹配不完备就不能使用上述方法了。因为在这种情况下可能存在点 \(z\) 使得虽然 \(u\) 和 \(v\) 各自连接的点 \(x\) 和 \(y\) 之间没有增广路径，但是存在从 \(x\) 到非匹配点 \(z\) 的增广路再到 \(y\) 的增广路。或者 \(u\) 或者 \(v\) 本身就是非匹配点，设 \(v\) 为非匹配点，此时断开 \(u\) 原先所连接的边连向 \(v\) 不影响最大匹配数。
解决这个问题的方法是，我们考虑根据二分图 \(G\) 建立 \(G'\) 的方法会发现 \(G'\) 其实就是上一个部分网络流二分图最大匹配去掉源点和汇点的部分。因为非匹配边的容量为 \(1\)，匹配边的反向边的容量为 \(1\)。
进一步考虑，对于当前的非匹配点 \(z\)，则 \(c_f(z, t) = 1\)，否则如果 \(v\) 为匹配点则 \(c_f(v, t) = 0, c_f(t, v) = 1\)。
因此残量网络中存在 \(z \to t \to v\) 的路径。若对于匹配边 \((u, v)\)，残量网络上 \(u\) 可以到达 \(z\) 那么 \(u\) 也可以到达 \(v\)。又因为 \(v \to u\) 是联通的，所以 \(u\) 和 \(v\) 就处于同一个强连通分量中。
从而我们得出：
· 必须边的判定条件为：\((u, v)\) 的流量为 \(1\)，并且在残量网络上属于不同的强连通分量。
· 可行边的判定条件为：\((u, v)\) 的流量为 \(1\)，并且在残量网络上属于相同的强连通分量。
例题
学会了这个我们就可以完成P10940 舞动的夜晚。
题目相当于让我们求二分图的不可行边数量且不保证二分图是完备匹配。那么我们只需要判断它不是可行边即可。
下面给出代码。
const int N = 20010, M = 300010;
int n, m, E, s, t;
int h[N], e[M], w[M], ne[M], now[N], idx;
int stk[N], in_stk[N], low[N], dfn[N], c[N], top, scc_cnt, timestamp;
int max_flow, flow, d[N];
queue<int> q;
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
e[idx] = a, w[idx] = 0, ne[idx] = h[b], h[b] = idx ++;
}
bool bfs() {
while (!q.empty()) q.pop();
memset(d, 0, sizeof d);
q.push(s); d[s] = 1, now[s] = h[s];
while (q.size()) {
int u = q.front(); q.pop();
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (w[i] && !d[v]) {
d[v] = d[u] + 1, now[v] = h[v];
q.push(v);
if (v == t) return true;
}
}
}
return false;
}
int dinic(int u, int flow) {
if (u == t) return flow;
int rest = flow, k;
for (int i = now[u]; ~i && rest; i = ne[i]) {
int v = e[i]; now[u] = i;
if (w[i] && d[v] == d[u] + 1) {
k = dinic(v, min(rest, w[i]));
if (!k) d[v] = 0;
rest -= k, w[i] -= k, w[i ^ 1] += k;
}
}
return flow - rest;
}
void tarjan(int u) {
dfn[u] = low[u] = ++ timestamp;
stk[++ top] = u, in_stk[u] = true;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (!w[i]) continue;
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (in_stk[v]) low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u]) {
scc_cnt ++; int k;
do {
k = stk[top --];
in_stk[k] = false, c[k] = scc_cnt;
} while (k != u);
}
}
int main() {
n = read(), m = read(), E = read();
memset(h, -1, sizeof h);
rep(i, 1, E) {
int a = read(), b = read();
add(a, b + n, 1);
}
s = 0, t = n + m + 1;
rep(i, 1, n) add(s, i, 1);
rep(i, 1, m) add(i + n, t, 1);
while (bfs())
while (flow = dinic(s, INF)) max_flow += flow;
rep(i, s, t) if (!dfn[i]) tarjan(i);
vector<int> ans;
for (int i = 0; i <= 2 * E; i += 2) {
int x = e[i ^ 1], y = e[i];
if (!w[i] || c[x] == c[y]) continue;
ans.push_back((i + 2) / 2);
}
printf("%d\n", ans.size());
for (auto x : ans) printf("%d ", x);
puts("");
return 0;
}
最小割
概念
顾名思义，容量之和最小的割。
最大流最小割定理
首先给出结论，最小割 \(=\) 最大流。
证明最小割等于最大流，我们可以先证明最小割大于等于最大流，然后再构造取等的方案。
对于网格 \(G = (V, E)\)，任意取一个流 \(f\) 和一个割 \(\{S, T\}\)，我们现在要证明 \(|f| \leq ||S, T||\)。
证明：
\(|f| = f(s) = \sum_{x \in V} f(s, x) - \sum_{x \in V} f(x, s) = \sum_{u \in S} f(u)\)
$ = \sum_{u \in S}(\sum_{v \in V}f(u, v) - \sum_{v \in V}f(v, u))$
$ = \sum_{u \in S}(\sum_{v\in T}f(u, v) + \sum_{v \in S}f(u, v) - \sum_{v\in T}f(v, u) - \sum_{v\in S}f(v, u)) $
$ = \sum_{u \in S}(\sum_{v\in T}f(u, v) - \sum_{v\in T}f(v, u)) + \sum_{u\in S}\sum_{v\in S} f(u, v) - \sum_{u\in S}\sum_{v\in S} f(v, u) $
$ \leq \sum_{u\in S}\sum_{v\in T} f(u, v) \leq \sum_{u\in S}\sum_{v\in T} c(u, v)$
$ = ||S, T||$
可以发现取等的条件是 \({(u, v) | u \in T, v \in S}\) 都为空流， \((v, u) | u \in S, v \in T\) 都为满流。
接下来考虑取等方案的构造，一种构造的方式是求出最大流后从源点开始沿残量网络 BFS，标记能到的点。则所有链接已标记点 \(u\) 和未标记点 \(v\) 的边就是网络的最小割。
所以最小割问题可以通过最大流解决。
最小割的可行边与必须边
可行边即所有割集的并，必须边即所有割集的交。
这里先给出可行边和必须边的判定条件。
可行边 \((u, v)\)：满流且残量网络中找不到 \(u \to v\) 的路径。
必须边 \((u,v)\)：满流且残量网络中源点能到入点，出点能到汇点。
先证明可行边的判定，根据最大流最小割定理的推导过程我们知道割集中的边都是满流。我们考虑残量网络中存在一条从 \(u\) 到 \(v\) 的路径，则此时加上残量网络中 \((u, v)\) 的反悔边就构成了一个环，那么 \(u \to v\) 的满流就可以在环上流动而不破坏最小割，但是破坏了满流。所以如果 \((u, v)\) 是一个可行边，那么 \(u\) 和 \(v\) 不能在一个强连通分量中。
关于必须边判定的证明，首先必须边一定是可行边的子集，一定满足不存在 \(u \to v\) 的路径。此时如果源点到不了入点说明在这条必须边前面一定有其它满流边堵塞了全部流量，那么这条必须边就不是唯一的了。出点到汇点也是同理。
由此，如果 \((u, v)\) 是一条必须边，那它一定满足 \(u\) 和源点在一个强连通分量中，\(v\) 与汇点在一个强连通分量中。
\(tarjan\) 一下就做完了。
可行边和必须边可以做一些神秘的题。
拆点
拆点是一个非常好用的技巧，体现在网络流上则是将网络上的每个点拆分为入点和出点，我们将点的所有入边连向入点，权值为 \(INF\)；将所有出边从出点出去，权值为 \(INF\)；再在入点和出点之间连一条边权值为 \(1\) 的边。
例题
我们以一道例题 SP300 CABLETV - Cable TV Network 为例，询问去掉多少个点可以使图不连通。
这其实是一个最小割模型，我们拆点后跑最小割即可。
const int N = 1010, M = 50010;
int n, m, s, t;
int h[N], e[M], w[M], ne[M], now[N], idx;
int max_flow, flow, d[N], a[N], b[N];
queue<int> q;
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
e[idx] = a, w[idx] = 0, ne[idx] = h[b], h[b] = idx ++;
}
bool bfs() {
while (!q.empty()) q.pop();
memset(d, 0, sizeof d);
q.push(s); d[s] = 1, now[s] = h[s];
while (q.size()) {
int u = q.front(); q.pop();
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (w[i] && !d[v]) {
d[v] = d[u] + 1, now[v] = h[v];
q.push(v);
if (v == t) return true;
}
}
}
return false;
}
int dinic(int u, int flow) {
if (u == t) return flow;
int rest = flow, k;
for (int i = now[u]; ~i && rest; i = ne[i]) {
int v = e[i]; now[u] = i;
if (w[i] && d[v] == d[u] + 1) {
k = dinic(v, min(rest, w[i]));
if (!k) d[v] = 0;
rest -= k, w[i] -= k, w[i ^ 1] += k;
}
}
return flow - rest;
}
void solve() {
n = read(), m = read();
memset(a, 0, sizeof a); memset(b, 0, sizeof b);
rep(k, 1, m) {
char s[10]; scanf("%s", s);
int i;
for (i = 1; isdigit(s[i]); i ++) a[k] = a[k] * 10 + s[i] - '0';
i ++;
for (; isdigit(s[i]); i ++) b[k] = b[k] * 10 + s[i] - '0';
}
int ans = INF;
for (s = 0; s < n; s ++)
for (t = 0; t < n; t ++) {
if (s == t) continue;
memset(h, -1, sizeof h); idx = 0;
rep(i, 0, n - 1)
if (i == s || i == t) add(i, i + n, INF);
else add(i, i + n, 1);
rep(i, 1, m) {
add(a[i] + n, b[i], INF);
add(b[i] + n, a[i], INF);
}
int maxflow, flow; maxflow = flow = 0;
while (bfs())
while (flow = dinic(s, INF)) maxflow += flow;
ans = min(ans, maxflow);
}
if (n <= 1 || ans == INF) ans = n;
printf("%d\n", ans);
}
int main() {
int T = read();
while (T --) solve();
return 0;
}
费用流
概念
我们在一般的网络中增加一个每条边 \((u, v)\) 的单位限制 \(w(u, v)\)，当 \((u, v)\) 的流量为 \(f(u, v)\) 时就要支付 \(f(u, v) \times w(u, v)\) 的费用。总花费最小的最大流叫做最小费用最大流，相对地，还有最大费用最大流。注意它们的前提都是最大流。
Edmons-Karp 增广路算法
我们在最大流部分讲过 EK 算法，在费用流问题中，我们只需要将 “BFS 寻找一条包含边数最少得增广路” 改为 “SPFA 寻找一条单位费用之和最小的增广路”即可。也就是将 \(w(u, v)\) 视为边权在残量网络上跑最短路，注意一条反向边 \((v, u)\) 的费用应该设为 \(-w(u, v)\)。
我们直接给出模板。(模板题为P3381 【模板】最小费用最大流)
const int N = 10010, M = 100010;
int n, m, s, t;
int h[N], e[M], ne[M], w[M], cost[M], idx;
int d[N], incf[N], pre[N], vis[N], maxflow, ans;
queue<int> q;
void add(int a, int b, int c, int f) {
e[idx] = b, w[idx] = c, cost[idx] = f, ne[idx] = h[a], h[a] = idx ++;
e[idx] = a, w[idx] = 0, cost[idx] = -f, ne[idx] = h[b], h[b] = idx ++;
}
bool spfa() {
memset(d, 0x7f, sizeof d); memset(vis, 0, sizeof vis);
while (!q.empty()) q.pop();
d[s] = 0, vis[s] = 1, incf[s] = 1 << 30; q.push(s);
while (!q.empty()) {
int u = q.front(); q.pop();
vis[u] = 0;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (!w[i]) continue;
if (d[v] > d[u] + cost[i]) {
d[v] = d[u] + cost[i], pre[v] = i;
incf[v] = min(incf[u], w[i]);
if (!vis[v]) vis[v] = 1, q.push(v);
}
}
}
if (d[t] == 0x7f7f7f7f) return false;
return true;
}
void upd() {
int x = t;
while (x != s) {
int i = pre[x];
w[i] -= incf[t], w[i ^ 1] += incf[t];
x = e[i ^ 1];
}
maxflow += incf[t];
ans += incf[t] * d[t];
}
int main() {
n = read(), m = read(), s = read(), t = read();
memset(h, -1, sizeof h);
while (m --) {
int a = read(), b = read(), c = read(), f = read();
add(a, b, c, f);
}
while (spfa()) upd();
printf("%d %d\n", maxflow, ans);
return 0;
}
例题
我们还是以一道题 P2045 方格取数加强版 为例。题目相当于方格取数但是要找 \(K\) 条路，其中每个点如果被多次经过只会贡献一次。
我们考虑直接将每个二维的点 \((i, j)\) 看做网络流上的一个点，然后拆点。我们定义一个点的入点为 \(u\)，出点为 \(u'\)，然后按照如下方式建图：
- 在 \(u\) 与 \(u'\) 之间连两条有向边，一条容量为 \(1\)，费用为格子内的数 \(c\)；另一条边容量为 \(K - 1\)，费用为 \(0\)。这样建图保证如果多次经过某个格子只会取 \(0\) 的费用。
- 设点 \(u, u'\) 表示 \((i, j)\)，则如果存在点 \((i + 1, j)\) 和 \((i, j + 1)\)，则从出点向它们连有向边，容量为 \(K\)，边权为 \(0\)。这样保证了找 \(K\) 条路的限制。
建完图后，以 \((1, 1)\) 为 \(s\)，\((n, n)\) 为 \(t\) 跑费用流就做完了。
const int N = 10010, M = 100010;
int n, k, s, t;
int h[N], e[M], ne[M], w[M], cost[M], idx;
int d[N], incf[N], pre[N], vis[N], maxflow, ans;
queue<int> q;
void add(int a, int b, int c, int f) {
e[idx] = b, w[idx] = c, cost[idx] = f, ne[idx] = h[a], h[a] = idx ++;
e[idx] = a, w[idx] = 0, cost[idx] = -f, ne[idx] = h[b], h[b] = idx ++;
}
int num(int a, int b, int c) {
return (a - 1) * n + b + c * n * n;
}
bool spfa() {
memset(d, 0xcf, sizeof d); memset(vis, 0, sizeof vis);
while (!q.empty()) q.pop();
d[s] = 0, vis[s] = 1, incf[s] = 1 << 30; q.push(s);
while (!q.empty()) {
int u = q.front(); q.pop();
vis[u] = 0;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (!w[i]) continue;
if (d[v] < d[u] + cost[i]) {
d[v] = d[u] + cost[i], pre[v] = i;
incf[v] = min(incf[u], w[i]);
if (!vis[v]) vis[v] = 1, q.push(v);
}
}
}
if (d[t] == 0xcfcfcfcf) return false;
return true;
}
void upd() {
int x = t;
while (x != s) {
int i = pre[x];
w[i] -= incf[t], w[i ^ 1] += incf[t];
x = e[i ^ 1];
}
maxflow += incf[t];
ans += incf[t] * d[t];
}
int main() {
n = read(), k = read();
memset(h, -1, sizeof h);
s = 0, t = 2 * n * n;
add(s, num(1, 1, 0), k, 0);
rep(i, 1, n) rep(j, 1, n) {
int x = read();
add(num(i, j, 0), num(i, j, 1), 1, x);
add(num(i, j, 0), num(i, j, 1), k - 1, 0);
if (i < n) add(num(i, j, 1), num(i + 1, j, 0), k, 0);
if (j < n) add(num(i, j, 1), num(i, j + 1, 0), k, 0);
}
while (spfa()) upd();
printf("%d\n", ans);
return 0;
}
上下界网络流
概念
对于流量 \(f(u, v)\) 我们限制它的上界和下界，即 \(b(u, v) \leq f(u, v) \leq c(u, v)\)。
无源汇上下界可行流
对于一个无源汇网络 \(G = (V, E)\)，询问是否存在某种标定每条边流量的方式使得每条边流量满足上下界限制并且流量平衡。
我们的做法是首先先将所有边跑满下界流量，然后再将其流量设为 \(c(u, v) - b(u, v)\)。此时会出现流量不平衡的情况，所以我们需要让出入流平衡。
我们设一个点的出流为 \(out_u\)，入流为 \(in_u\)，同时建立虚拟源汇点 \(s'\) 和 \(t'\)，分三种情况讨论：
- \(out_u < in_u\)，多流进了流量所以源点要分走一些，即连边 \((s, u, in_x - out_x)\)。
- \(out_u = in_u\)，平衡，不需要操作。
- \(out_u > in_u\)，多流出了流量所以要给一些到汇点，即连边 \((u, t, out_x - in_x)\)
这里给出一幅图（来自Jeanny）。
我们在建出来的图上跑最大流，如果从 \(s'\) 流出的边均为满流，则说明找到了可行流，反之则没有可行流。
上图明显没有可行流。
模板题
代码戳这里喵\(\to\)提交记录
有源汇上下界可行流
顾名思义拥有 \(s\) 和 \(t\)。注意到从 \(s\) 流出的流一定等于流入 \(t\) 的流，所以我们可以从 \(t\) 到 \(s\) 连一条边使得 \(b(t, s) = 0, c(t, s) = \infty\)。然后直接跑无源汇上下界可行流即可。
注意我们一定要新建虚拟源汇，不能直接使用原图的 \(s\) 和 \(t\)。
有源汇上下界最大流
首先要知道最大流 \(=\) 可行流 + 可以向上浮动的部分，即在可行流的基础上尽量跑满上限。所以我们先跑一遍可行流，这时在 \(s'\) 和 \(t'\) 一定都满流了，所以我们在删除所有附加边的残量网络上继续找增广路做最大流即可。
模板题
代码戳这里喵\(\to\)提交记录
有源汇上下界最小流
我们考虑最大流是要尽可能搞更多的流量，那最小流就是要退掉尽可能多的流。所以我们只需要在删除所有附加边的残量网络上从 \(t\) 到 \(s\) 跑最大流，然后用可行流减去最大流即可得到答案。
注意求出可行流后应该删掉边 \((T, S, \infty)\)。
模板题
代码戳这里喵\(\to\)提交记录
浙公网安备 33010602011771号