二分图与网络流 学习笔记
xht
2019-03-14 22:39:23
> 本文进行了全文更新。
>
> 本文包括了二分图与网络流的绝大部分重要知识点，限于篇幅~~和作者水平~~，本文省略了较多的证明过程和推导过程。
>
> **学习二分图与网络流，最重要的是大量的刷题。**在更新时，作者思索再三，决定删掉所有【练习】。一个原因是，原本的习题结构太乱，并没有很好的参考价值；另一个原因是，实际上「找题刷」的过程本身就充满乐趣，同时也并不难找。
## 二分图
如果一张无向图 $(V, E)$ 存在点集 $A,B$，满足 $|A|,|B| \ge 1$，$A \cap B = \varnothing$，$A \cup B = V$，且对于 $x,y \in A$ 或 $x,y \in B$，$(x,y) \notin E$，则称这张无向图为一张**二分图**，$A,B$ 分别为二分图的**左部**和**右部**。
### 二分图判定
#### 定理
一张无向图是二分图，当且仅当图中无**奇环**。
#### 染色法
时间复杂度 $\mathcal O(n)$。
```cpp
const int N = 1e6 + 7;
int n, m, v[N];
vi e[N];
bool dfs(int x, int c) {
v[x] = c;
for (int y : e[x]) {
if (v[y] == c) return 0;
if (!v[y] && !dfs(y, 3 - c)) return 0;
}
return 1;
}
int main() {
rd(n), rd(m);
for (int i = 1, x, y; i <= m; i++)
rd(x), rd(y), e[x].pb(y), e[y].pb(x);
for (int i = 1; i <= n; i++)
if (!v[i] && !dfs(i, 1)) return prints("No"), 0;
prints("Yes");
return 0;
}
```
##### 【例题】[P1525 关押罪犯](https://www.luogu.com.cn/problem/P1525)
这道题有一种**扩展域并查集**的解法，在此不赘述。
题意抽象出来的模型就是：
> 给定一张无向图，边有边权。
> 找到最小的权值 $k$，使得只保留权值 $> k$ 的边时，图是一张二分图。
二分答案，二分图染色判定即可。
### 二分图最大匹配
#### 图的匹配
对于一张无向图 $(V, E)$，若存在一个边集 $E^{\prime}$，满足 $E^{\prime} \subseteq E$，且对于任意 $p,q \in E^{\prime}$，$p,q$ 没有公共端点，则称 $E^{\prime}$ 为这张无向图的一组**匹配**。
#### 二分图最大匹配
在二分图中，包含边数最多的一组匹配被称为二分图的**最大匹配**。
#### 其他相关定义
对于任意一组匹配 $S$，属于 $S$ 的边被称为**匹配边**，不属于 $S$ 的边被称为**非匹配边**。
匹配边的端点被称为**匹配点**，其他点被称为**非匹配点**。
如果二分图中存在一条连接两个**非匹配点**的路径 $path$ ，使得非匹配边与匹配边在 $path$ 上交替出现，那么称 $path$ 是匹配 $S$ 的**增广路**。
#### 增广路的性质
1. 长度为**奇数**。
2. 奇数边是非匹配边，偶数边是匹配边。
3. **如果把路径上所有边的状态（是否为匹配边）取反，那么得到的新的边集 $S^{\prime}$ 仍然是一组匹配，并且匹配的边数增加了 $1$。**
#### 结论
**二分图的一组匹配 $S$ 是最大匹配，当且仅当图中不存在 $S$ 的增广路。**
### 匈牙利算法
#### 主要过程
1. 初始时设 $S$ 为空集，即所有边都是非匹配边。
2. 寻找增广路 $path$，把 $path$ 上所有边的匹配状态取反，得到一个更大的匹配 $S^{\prime}$。
3. 重复第 2 步，直到图中不存在增广路。
#### 寻找增广路
依次尝试给每一个左部点 $x$ 寻找一个匹配的右部点 $y$。
$y$ 与 $x$ 匹配需满足下面两个条件之一：
1. $y$ 是非匹配点。
2. $y$ 已与 $x^\prime$ 匹配，但从 $x^\prime$ 出发能找到另一个 $y^\prime$ 与之匹配。
#### 时间复杂度
$\mathcal O(nm)$。
##### 【模板】[P3386 【模板】二分图匹配](https://www.luogu.com.cn/problem/P3386)
```cpp
const int N = 2e3 + 7;
int n, m, t, f[N], ans;
bool v[N];
vi e[N];
bool dfs(int x) {
for (int y : e[x])
if (!v[y]) {
v[y] = 1;
if (!f[y] || dfs(f[y])) return f[y] = x, 1;
}
return 0;
}
int main() {
rd(n), rd(m), rd(t);
for (int i = 1, x, y; i <= t; i++) {
rd(x), rd(y);
if (x > n || y > m) continue;
e[x].pb(y + n), e[y+n].pb(x);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n + m; j++) v[j] = 0;
ans += dfs(i);
}
print(ans);
return 0;
}
```
#### 二分图匹配模型的两个要素
1. 点能分成两个集合，每个集合内部有 $0$ 条边。简称 $0$ 要素。
2. 每个点只能与 $1$ 条匹配边相连。简称 $1$ 要素。
##### 【例题】[U64949 棋盘覆盖](https://www.luogu.com.cn/problem/U64949)
> 给定一个 $n$ 行 $n$ 列的棋盘，有 $m$ 个格子禁止放置。
> 求最多能不重叠地往棋盘上放多少块长度为 $2$ 宽度为 $1$ 的骨牌。
- $1$ 要素：每个格子只能被一张骨牌覆盖，一张骨牌覆盖 $2$ 个相邻的格子。
把棋盘上没有被禁止的格子作为**点**，骨牌作为**边**（两个相邻的格子对应的点之间连边）。
- $0$ 要素：把棋盘黑白相间染色，相同颜色的格子不可能被同一骨牌覆盖。
那么，若把白色格子作为左部点，黑色格子作为右部点，则刚才建立的无向图是二分图。
使用匈牙利算法求上述二分图的最大匹配，时间复杂度为 $\mathcal O(n^2m^2)$。
##### 【例题】[U64965 車的放置](https://www.luogu.com.cn/problem/U64970)
> 車的攻击范围为同一行或同一列的其他棋子。
> 给定一个 $n$ 行 $m$ 列的棋盘，有 $t$ 个格子禁止放置。
> 求最多能放多少个不能互相攻击的車。
- $1$ 要素：每行、每列只能放 $1$ 个車。
把行、列作为**点**，如果一个格子没有被禁止，则在此格子所在行和列对应的点连**边**。
- $0$ 要素：行节点之间没有边，列节点之间也没有边。
那么，若把行节点作为左部点，列节点作为右部点，则刚才建立的无向图是二分图。
使用匈牙利算法求上述二分图的最大匹配，时间复杂度为 $\mathcal O((n+m)nm)$。
### 特殊的二分图匹配
#### 完备匹配
对于一张二分图 $((A, B), E)$，设其最大匹配为 $E^{\prime}$，若 $|A| = |B| = |E^{\prime}|$，则称这张二分图具有**完备匹配**。
#### 多重匹配
对于一张二分图 $((A, B), E)$，从 $E$ 中选出尽量多的边，使 $x \in A$ 最多与 $l_x$ 条选出的边相连，$y \in B$ 最多与 $r_y$ 条选出的边相连，则称选出的边为二分图的**多重匹配**。
方法有两个。
一是拆点求解二分图最大匹配，即将每个 $x \in A$ 拆成 $l_x$ 个点，每个 $y \in B$ 拆成 $r_y$ 个点。
二是网络流，见后文。
#### 最优匹配
对于一张二分图，边有边权，所有**最大匹配**中边权总和最大的，被称为**最优匹配**。
方法同样有两个。
一是 KM 算法，本文选择不介绍，感兴趣的读者可自行研究。
二是费用流，同样见后文。
### 二分图最小点覆盖
#### 图的点覆盖
对于一张无向图 $(V, E)$，若存在一个点集 $V^{\prime}$，满足 $V^{\prime} \subseteq V$，且对于任意 $e \in E$，$e$ 至少有一个端点属于 $V^{\prime}$，则称 $V^{\prime}$ 为这张无向图的一组**点覆盖**。
#### 二分图最小点覆盖
在二分图中，包含点数最少的一组点覆盖被称为二分图的**最小点覆盖**。
#### 定理
从定义上即可发现，**匹配**和**点覆盖**是很相似的。
实际上在二分图中，最小点覆盖包含的点数，等于最大匹配包含的边数。
#### 二分图最小点覆盖模型的一个要素
1. 每条边有两个端点，二者至少选择一个。简称 $2$ 要素。
##### 【例题】[UVA1194 Machine Schedule](https://www.luogu.com.cn/problem/UVA1194)
> 有两台机器 $A,B$，它们分别有 $n,m$ 种模式。
> 有 $k$ 个任务，第 $i$ 个任务在 $A,B$ 上执行的模式为 $a_i,b_i$。
> 任务可以以任意顺序被执行，但每台机器转换一次模式就要重启一次。
> 求怎样分配任务并合理安排顺序，能使机器重启次数最少。
- $2$ 要素：每个任务要么在 $A$ 上以 $a_i$ 模式执行，要么在机器 $B$ 上以 $b_i$ 模式执行。
把 $A,B$ 的 $n,m$ 种模式分别作为 $n$ 个左部点和 $m$ 个右部点，每个任务作为边连接左部点 $a_i$ 和右部点 $b_i$。
求这张二分图的最小点覆盖，时间复杂度为 $\mathcal O(nm)$。
##### 【例题】[POJ2226 Muddy Fields](http://poj.org/problem?id=2226)
> 在一块 $n \times m$ 的地面上，有一些格子是泥泞的，有一些格子是干净的。
> 现在需要用一些宽度为 $1$ 长度任意的木板把泥地盖住，同时不能盖住干净的地面，木板可以重叠。
> 求最少需要多少块木板。
- $2$ 要素：每块泥地要么被横着的木板盖住，要么被竖着的木板盖住。
横着的木板只能放在同一行若干个连续的泥地上，称这种连续的泥地为**行泥泞块**；竖着的木板只能放在同一列若干个连续的泥地上，称这种连续的泥地为**列泥泞块**。
把行泥泞块作为左部，列泥泞块作为右部点。对于每块泥地，在其对应的行泥泞块和列泥泞块之间连边。
求出这张二分图的最小点覆盖即可。
### 二分图最大独立集
#### 图的独立集
对于一张无向图 $(V, E)$，若存在一个点集 $V^{\prime}$，满足 $V^{\prime} \subseteq V$，且对于任意 $p,q \in V^{\prime}$，$(p,q) \notin E$，则称 $V^{\prime}$ 为这张无向图的一组**独立集**，包含点数最多的独立集被称为图的**最大独立集**。
#### 图的团
对于一张无向图 $(V, E)$，若存在一个点集 $V^{\prime}$，满足 $V^{\prime} \subseteq V$，且对于任意 $p,q \in V^{\prime}$，$(p,q) \in E$，则称 $V^{\prime}$ 为这张无向图的一组**团**，包含点数最多的团被称为图的**最大团**。
#### 定理
无向图 $G$ 的最大团，等于补图 $G^\prime$ 的最大独立集。
对于一般无向图，最大团、最大独立集是 NPC 问题。
#### 二分图最大独立集
在二分图中，包含点数最多的一组独立集被称为二分图的**最大独立集**。
#### 定理
对于一张 $n$ 个点的二分图，最大独立集大小，等于 $n-$ 最小点覆盖点数，等于 $n-$ 最大匹配边数。
##### 【例题】[P3355 骑士共存问题](https://www.luogu.com.cn/problem/P3355)
> 骑士的攻击范围为「日」字对角的其他棋子。
> 给定一个 $n$ 行 $n$ 列的棋盘，有 $m$ 个格子是障碍。
> 求最多能放多少个不能互相攻击的骑士。
黑白相间染色棋盘，把黑、白色格子分别作为左、右部点，则「日」字对角的两个点颜色一定不同。
若两个格子是「日」字对角，则在对应的点之间连边。
求上述二分图的最大独立集即可。
**注意：本题匈牙利算法无法 AC，正解为网络流，见后文。**
##### 【例题】[P2423 [HEOI2012]朋友圈](https://www.luogu.com.cn/problem/P2423)
> 一张无向图有 $A,B$ 两类点，$A$ 类点有权值 $a$，$B$ 类点有权值 $b$。
> 若 $x,y \in A$ 且 $a_x \operatorname{xor} a_y \bmod 2 = 1$，则 $x,y$ 之间有边。
> 若 $x,y \in B$ 且 $b_x \operatorname{xor} b_y \bmod 2 = 0$ 或 $\operatorname{count}(b_x \operatorname{or} b_y) \bmod 2 = 1$，则 $x,y$ 之间有边，其中 $\operatorname{count}(x)$ 表示 $x$ 在二进制下 $1$ 的个数。
> 另外给定 $m$ 条边 $(x,y)$，保证 $x \in A$ 且 $y \in B$。
> 求这张图的最大团。
观察原图，$A$ 中权值奇偶性不同的点之间有边，$B$ 中所有奇数权值的点之间有边、所有偶数权值的点之间有边、权值奇偶性不同的点之间一部分有边。
一般图的最大团问题是 NPC 的，然而这张图的补图很特殊。
观察补图，$A$ 中奇数权值的点构成完全图、偶数权值的点构成完全图，$B$ 中奇数权值的点和偶数权值的点构成二分图。
由于无向图的最大团，等于补图的最大独立集。
因此 $A$ 中最多取两个点，可以枚举这两个点 $x,y$，删除与 $x$ 或 $y$ 之间无边的 $B$ 中的点，然后在 $B$ 中剩余的点上求二分图的最大独立集即可。
### 有向无环图的最小路径点覆盖
给定一张**有向无环图**，用尽量少的不相交的简单路径覆盖所有点（也就是每个点恰好被覆盖一次），这样的路径集合被称为**最小路径点覆盖**。
#### 拆点二分图
把每个点拆成编号为 $x$ 和 $x + n$ 的两个点。
建立一张新的二分图，$1 \sim n$ 是左部点，$n + 1 \sim 2n$ 是右部点。
对原图的每条有向边 $(x,y)$，在二分图的左部点 $x$ 与右部点 $y + n$ 之间连边。
最终得到的二分图成为原图的**拆点二分图**。
#### 定理
有向无环图的最小路径点覆盖包含的路径条数，等于 $n-$ 拆点二分图的最大匹配边数。
##### 【模板】[P2764 最小路径覆盖问题](https://www.luogu.com.cn/problem/P2764)
#### 有向无环图的最小可重复路径点覆盖
给定一张**有向无环图**，用尽量少的可相交的简单路径覆盖所有点（也就是每个顶点可以被覆盖多次），这样的路径集合被称为**有向无环图的最小可重复路径点覆盖**。
方法：对有向图进行**传递闭包**，转化为**最小路径点覆盖**即可。
## 网络流
一个**网络** $G = (V,E)$ 是一张有向图，图中每条有向边 $(x,y) \in E$ 都有一个给定的权值 $c(x,y)$，称为边的**容量**。特别地，若 $(x,y) \notin E$，则 $c(x,y) = 0$。图中还有两个指定的特殊节点 $S,T \in V(S \neq T)$，分别被称为**源点**和**汇点**。
设 $f(x,y)$ 是定义在节点二元组 $(x,y \in V)$ 上的实数函数，且满足：
1. **容量限制**：$f(x,y) \leq c(x,y)$。
2. **斜对称**：$f(x,y)=-f(y,x)$。
3. **流量守恒**：任意 $x \neq S,x \neq T$，$\sum_{(u,x)\in E} f(u,x) = \sum_{(x,v)\in E} f(x,v)$。
则 $f$ 称为网络的**流**函数。
对于 $(x,y) \in E$，$f(x,y)$ 称为边的**流量**，$c(x,y) - f(x,y)$ 称为边的**剩余流量**。
$\sum_{(S,v) \in E} f(S,v)$ 称为整个网络的**流量**。
> 通俗地讲，我们想象一下自来水厂到你家的水管网是一个复杂的有向图，每一节水管都有一个最大承载流量。
> 自来水厂不放水，你家就断水了。但是就算自来水厂拼命地往管网里面注水，你家收到的水流量也是上限，毕竟每根水管承载量有限。
> 你想知道你能够拿到多少水，这就是一种网络流问题。
### 最大流
对于一个给定的网络，使整个网络的流量最大的合法的流函数被称为网络的**最大流**，此时的流量被称为网络的**最大流量**。
简单地讲，就是上面那个问题。
### EK 增广路算法
**增广路**是指从 $S$ 到 $T$ 的一条路径，流过这条路径，使得当前的流量可以增加。
**那么求最大流问题可以转换为不断找增广路的问题，并且当图中不存在增广路时就达到了最大流。**
找增广路时，直接暴力从 $S$ 到 $T$ 广搜即可，从 $S$ 开始不断向外广搜，通过剩余流量大于 $0$ 的边，直到找到 $T$ 为止。
找到增广路之后，记增广路上的最小剩余流量为 $f$，则最大流加上 $f$，增广路上的每一条边的剩余流量减去 $f$，**增广路上的每一条边的反向边的剩余流量加上 $f$**。
时间复杂度 $\mathcal O(nm^2)$，实际运用中远远达不到，能够处理 $10^3 \sim 10^4$ 规模的网络。
### Dinic 算法
#### 残量网络
在任意时刻，网络中所有节点以及剩余容量大于 $0$ 的边构成的子图被称为**残量网络**。
EK 算法每轮可能会遍历整个残量网络，但只找出一条增广路，就很浪费。
#### 分层图
将图分层，节点深度 $d_x$ 表示 $S$ 到 $x$ 最少需要经过的边数。
在残量网络中，满足 $d_y = d_x + 1$ 的边 $(x,y)$ 构成的子图被称为**分层图**。
显然，分层图是一张**有向无环图**。
#### Dinic 算法
不断重复以下步骤，直到残量网络中 $S$ 不能到达 $T$：
1. 在残量网络上 BFS 求出节点层次，构造分层图。
2. 在分层图上 DFS 寻找增广路，在回溯时实时更新剩余容量。另外，每个点可以流向多条出边，同时还加入若干剪枝及优化。
时间复杂度 $\mathcal O(n^2m)$，**不加剪枝和优化复杂度是错的**，实际运用中远远达不到，能够处理 $10^4 \sim 10^5$ 规模的网络。
##### 【模板】[P3376 【模板】网络最大流](https://www.luogu.com.cn/problem/P3376)
```cpp
namespace Dinic {
const int N = 1e5 + 7, M = 1e6 + 7;
const ll inf = 1e18;
int n, S, T, h[N], hi[N], e[M], t[M], tot, d[N];
ll mxf, f[M];
inline void add(int x, int y, ll z, int o = 1) {
e[++tot] = y, f[tot] = z, t[tot] = h[x], h[x] = tot;
if (o) add(y, x, 0, 0);
}
inline bool bfs() {
for (int i = 1; i <= n; i++) d[i] = 0;
queue<int> q;
q.push(S), d[S] = 1;
while (q.size()) {
int x = q.front();
q.pop();
for (int i = h[x]; i; i = t[i]) {
int y = e[i];
ll z = f[i];
if (d[y] || !z) continue;
q.push(y), d[y] = d[x] + 1;
if (y == T) return 1;
}
}
return 0;
}
ll dinic(int x, ll nwf) {
if (x == T) return nwf;
ll rst = nwf;
for (int &i = hi[x]; i; i = t[i]) {
int y = e[i];
ll z = f[i];
if (d[y] != d[x] + 1 || !z) continue;
ll k = dinic(y, min(z, rst));
if (!k) d[y] = 0;
else f[i] -= k, f[i^1] += k, rst -= k;
if (!rst) break;
}
return nwf - rst;
}
inline void main() {
while (bfs()) {
for (int i = 1; i <= n; i++) hi[i] = h[i];
ll now;
while ((now = dinic(S, inf))) mxf += now;
}
}
inline void init(int _n, int _S, int _T) {
n = _n, S = _S, T = _T, tot = 1, mxf = 0;
for (int i = 1; i <= n; i++) h[i] = 0;
}
}
int main() {
int n, m, S, T;
rd(n), rd(m), rd(S), rd(T), Dinic::init(n, S, T);
for (int i = 1, x, y, z; i <= m; i++)
rd(x), rd(y), rd(z), Dinic::add(x, y, z);
Dinic::main();
print(Dinic::mxf);
return 0;
}
```
#### 最大流解决二分图多重匹配
新建一个源点 $S$ 和一个汇点 $T$，从 $S$ 向每个左部点 $x$ 连一条容量为 $l_x$ 的边，从每个右部点 $y$ 向 $T$ 连一条容量为 $r_y$ 的边，把原二分图的每条边看作从左部点到右部点连的一条容量为 $1$ 的边。
那么，二分图多重匹配边数，就等于网络最大流。
Dinic 算法在**由二分图通过上述方法构造出来的网络**中时间复杂度为 $\mathcal O(m \sqrt n)$，比匈牙利算法快，实际表现则更快。
### 二分图最大匹配的必须边与可行边
#### 最大匹配是完备匹配
把二分图中的非匹配边看作从左部向右部的有向边，匹配边看作从右部向左部的有向边，构成一张新的有向图。
- 必须边 $(x,y)$：$(x,y)$ 是当前二分图的匹配边，且 $x,y$ 在新的有向图中属于不同的强连通分量。
- 可行边 $(x,y)$：$(x,y)$ 是当前二分图的匹配边，或 $x,y$ 在新的有向图中属于同一个强连通分量。
#### 最大匹配不一定是完备匹配
- 必须边 $(x,y)$：$(x,y)$ 的流量为 $1$，且在残量网络上属于不同的强连通分量。
- 必须边 $(x,y)$：$(x,y)$ 的流量为 $1$，或在残量网络上属于同一个强连通分量。
### 最小割
给定一个网格 $G=(V,E)$，源点为 $S$，汇点为 $T$。
若一个边集被删去后，源点 $S$ 和汇点 $T$ 不再连通，则称该边集为网络的**割**。
边的容量之和最小的割称为网络的**最小割**。
#### 最大流最小割定理
最大流等于最小割。
#### 点边转化
##### 【例题】[UVA1660 电视网络 Cable TV Network](https://www.luogu.com.cn/problem/UVA1660)
> 给定一张 $n$ 个点的无向图。
> 求最少删除多少个点，使得图不连通。
枚举两个不直接连通的点 $S$ 和 $T$，求在剩余的 $n-2$ 个节点中最少去掉多少个可以使 $S$ 和 $T$ 不连通，所有答案的 $\min$ 就是答案。
考虑点边转化，把原来无向图中的每个点 $x$，拆成入点 $x$ 和出点 $x^\prime$，则在无向图中删去一个点，等价于在网络中断开 $(x,x^\prime)$。
对任意 $x \neq S$ 且 $x \neq T$ 的点 $x$ 连有向边 $(x,x^\prime)$，容量为 $1$。
对原无向图的每条边 $(x,y)$，连有向边 $(x^\prime,y)$ 和 $(y^\prime,x)$，容量为 $+ \infty$，即防止割断。
求最小割即可。
当然，在点边转化中也可以将一条边截成两半，中间插入一个点，把边的各种信息反映在这个点上。
#### 集合划分模型
> 有 $n$ 个物品和两个集合 $S,T$。
> 如果将一个物品放入 $S$ 集合会花费 $a_i$，放入 $T$ 集合会花费 $b_i$。
> 还有若干个形如 $u,v,w$ 限制条件，表示如果 $u$ 和 $v$ 同时不在一个集合会花费 $w$。
> 每个物品必须且只能属于一个集合，求最小的代价。
我们对于每个集合设置源点 $S$ 和汇点 $T$，第 $i$ 个点由 $S$ 连一条容量为 $b_i$ 的边、向 $T$ 连一条容量为 $a_i$ 的边。对于限制条件 $u,v,w$，我们在 $u,v$ 之间连容量为 $w$ 的双向边。
注意到当 $S$ 和 $T$ 不相连时，$S$ 能到达 $i$ 代表物品 $i$ 放入 $S$，$i$ 能到达 $T$ 代表物品 $i$ 放入 $T$。
当割开 $S \to i$ 的边，意味着 $i$ 放入 $T$；当割开 $i \to T$ 的边，意味着 $i$ 放入 $S$；当割开 $u,v$ 之间的边，意味着 $u,v$ 不放入同一个集合。
因此最小割就是最小花费。
##### 【例题】[P2057 [SHOI2007]善意的投票 / [JLOI2010]冠军调查](https://www.luogu.com.cn/problem/P2057)
连边：
1. $i$ 意愿为 $0$，$(S, i, 1)$，$(i,T,0)$（可省略）。
2. $i$ 意愿为 $1$，$(S,i,0)$（可省略），$(i,T,1)$。
3. $i,j$ 是朋友，$(i,j,1)$，$(j,i,1)$。
跑最大流即可。
#### 最小割的可行边与必须边
首先求最大流，那么最小割的可行边与必须边都必须是**满流**。
- 可行边 $(x,y)$：在残量网络中不存在 $x$ 到 $y$ 的路径。
- 必须边 $(x,y)$：在残量网络中 $S$ 能到 $x$ 且 $y$ 能到 $T$。
##### 【模板】[P4126 [AHOI2009]最小割](https://www.luogu.com.cn/problem/P4126)
#### 平面图最小割
边与边只在顶点相交的图被称为**平面图**。
对于一个平面图，都有其对应的**对偶图**：
- 平面图被划分出的每一个区域当作对偶图的一个点；
- 平面图中的每一条边两边的区域对应的点用边相连，特别地，若两边为同一区域则加一条回边（自环）。
这样构成的图即为原平面图的对偶图。
**平面图最小割等于对偶图最短路。**
##### 【模板】[P4001 [ICPC-Beijing 2006]狼抓兔子](https://www.luogu.com.cn/problem/P4001)
### 费用流
给定一个网络 $G = (V,E)$，每条边 $(x,y)$ 除了有容量限制 $c(x,y)$，还有一个单位费用 $w(x,y)$。
当边 $(x,y)$ 的流量为 $f(x,y)$ 时，有花费 $f(x,y) \times w(x,y)$。
该网格中总花费最小的最大流被称为**最小费用最大流**，总花费最大的最大流被称为**最大费用最大流**。
#### EK 增广路算法
在 EK 增广路算法求解最大流的基础上，把 BFS 改为 SPFA，把 $w(x,y)$ 当作边权，在残量网络上求最短路，即可求出最小费用最大流。注意：一条反向边边权应为其正向边边权的相反数。
##### 【模板】[P3381 【模板】最小费用最大流](https://www.luogu.com.cn/problem/P3381#sub)
```cpp
namespace EK {
const int N = 1e4 + 7, M = 1e5 + 7;
const ll inf = 1e18;
int n, S, T, h[N], e[M], t[M], tot, pre[N], v[N];
ll mxf, ans, f[M], c[M], d[N], now[N];
inline void add(int x, int y, ll z, ll w, int o = 1) {
e[++tot] = y, f[tot] = z, c[tot] = w, t[tot] = h[x], h[x] = tot;
if (o) add(y, x, 0, -w, 0);
}
inline bool spfa() {
for (int i = 1; i <= n; i++) v[i] = 0, d[i] = inf;
queue<int> q;
q.push(S), v[S] = 1, d[S] = 0, now[S] = inf;
while (q.size()) {
int x = q.front();
q.pop(), v[x] = 0;
for (int i = h[x]; i; i = t[i]) {
int y = e[i];
ll z = f[i], w = c[i];
if (!z || d[y] <= d[x] + w) continue;
d[y] = d[x] + w, now[y] = min(now[x], z), pre[y] = i;
if (!v[y]) q.push(y), v[y] = 1;
}
}
return d[T] != inf;
}
inline void upd() {
mxf += now[T], ans += d[T] * now[T];
int x = T;
while (x != S)
f[pre[x]] -= now[T], f[pre[x]^1] += now[T], x = e[pre[x]^1];
}
inline void main() {
while (spfa()) upd();
}
inline void init(int _n, int _S, int _T) {
n = _n, S = _S, T = _T, tot = 1, mxf = ans = 0;
for (int i = 1; i <= n; i++) h[i] = 0;
}
}
int main() {
int n, m, S, T;
rd(n), rd(m), rd(S), rd(T);
EK::init(n, S, T);
for (int i = 1, x, y, z, w; i <= m; i++)
rd(x), rd(y), rd(z), rd(w), EK::add(x, y, z, w);
EK::main();
print(EK::mxf, ' '), print(EK::ans);
return 0;
}
```
#### 最大费用最大流解决二分图带权最大匹配
类似最大流解决二分图多重匹配，每条边的权值就是他的单位费用。
##### 【例题】[P2045 方格取数加强版](https://www.luogu.com.cn/problem/P2045)
> 给定一个 $n \times n$ 的矩阵，每一格有一个非负整数 $a_{i,j}$。
> 现在从 $(1,1)$ 出发，可以往右或者往下走，最后到达 $(n,n)$。
> 每到达一格，把该格子的数取出来，该格子的数就变成 $0$。
> 这样一共走 $k$ 次，现在要求 $k$ 次所达到的方格的数的和最大。
1. 点边转化：把每个格子 $(i,j)$ 拆成一个入点一个出点。
2. 从每个入点向对应的出点连两条有向边：一条容量为 $1$，费用为格子 $a_{i,j}$；另一条容量为 $k-1$，费用为 $0$。
3. 从 $(i,j)$ 的出点到 $(i,j+1)$ 和 $(i+1,j)$ 的入点连有向边，容量为 $k$，费用为 $0$。
4. 以 $(1,1)$ 的入点为源点，$(n,n)$ 的出点为汇点，求最大费用最大流。
#### 费用提前计算
##### 【例题】[P2053 [SCOI2007]修车](https://www.luogu.com.cn/problem/P2053)
> 有 $n$ 辆车要维修，有 $m$ 位技术人员，第 $i$ 辆车由第 $j$ 位技术人员维修所用的时间为 $t_{i,j}$。
> 现在需要安排这 $m$ 位技术人员所维修的车及顺序，使得顾客平均等待的时间最小。
注意到每位车主的等待时间除了跟自己的车所需的维修时间有关之外，还跟同一位技术人员之前维修所花的时间有关，这导致我们很难直观地建模。
但是仔细观察可以发现，一个人维修所花的时间，对同一位技术人员之后的维修造成的影响是已知且固定的。
那么，我们将费用提前计算。即将第 $i$ 位车主的车由第 $j$ 位维修人员倒数第 $k$ 个维修所花的时间（费用）当作 $k \times t_{i,j}$。
从源点向每位车主连边，容量为 $1$，费用为 $0$。
每位维修人员拆成 $n$ 个点，向汇点连边，容量为 $1$，费用为 $0$。
第 $i$ 位车主向第 $j$ 位维修人员拆成的第 $k$ 个点连边，容量为 $1$，费用为 $k \times t_{i,j}$。
求最小费用最大流即可。
#### 动态开点
##### 【例题】[P2050 [NOI2012]美食节](https://www.luogu.com.cn/problem/P2050)
> 上一题的加强版。
同上一题一样建图，但是硬求最小费用最大流只能拿到 $60$ 分。
考虑动态开点，起初每个人只拆成一个点，每次增广时拆出一个新点即可。
### 上下界网络流
#### 无源汇上下界可行流
##### 【模板】[LOJ115 无源汇有上下界可行流](https://loj.ac/problem/115)
> 给定一个 $n$ 个点，$m$ 条边的网络，求一个可行解，使得第 $i$ 条边 $(x_i, y_i)$ 的流量介于 $[l_i, r_i]$ 之间，并且整个网络满足流量守恒。
如果把 $r-l$ 作为容量上界，$0$ 作为容量下界，就是一般的网络流模型。
然而求出的实际流量为 $f_i + l_i$，不一定满足流量守恒，需要调整。
设 $d_{u}^{in} = \sum_{y_i = u} l_i$，$d_{u}^{out} = \sum_{x_i = u} l_i$，$d_u=d_{u}^{in}-d_{u}^{out}$。
新建源汇 $S,T$，$S$ 向 $d>0$ 的点连边，$d<0$ 的点向 $T$ 连边，容量为相应的 $d$。设 $s$ 为 $S$ 向外连边的流量和，显然 $s$ 也是向 $T$ 连边的流量和。
在该网络上求最大流，若最大流为 $s$，则每条边的流量 $+$ 下界就是原网络的一个可行流，否则无解。
具体实现时，可省略 $d_{u}^{in},d_{u}^{out}$ 数组，直接在 $d$ 数组上修改。
```cpp
namespace no_ok_flow {
const int N = 1e5 + 7;
int n, S, T;
ll d[N], s;
inline void add(int x, int y, ll l, ll r) {
Dinic::add(x, y, r - l), d[y] += l, d[x] -= l;
}
inline bool main() {
for (int i = 1; i <= n; i++)
if (d[i] > 0) Dinic::add(S, i, d[i]), s += d[i];
else if (d[i] < 0) Dinic::add(i, T, -d[i]);
Dinic::main();
return Dinic::mxf == s;
}
inline void init(int _n) {
n = _n, s = 0, S = n + 1, T = n + 2;
Dinic::init(n + 2, S, T);
for (int i = 1; i <= n; i++) d[i] = 0;
}
}
const int M = 10207;
int n, m, l[M];
int main() {
rd(n), rd(m);
no_ok_flow::init(n);
for (int i = 1, x, y, l, r; i <= m; i++)
rd(x), rd(y), rd(l), rd(r), no_ok_flow::add(x, y, l, r), ::l[i] = l;
if (!no_ok_flow::main()) return prints("NO"), 0;
prints("YES");
for (int i = 1, j = 3; i <= m; i++, j += 2) print(l[i] + Dinic::f[j]);
return 0;
}
```
#### 有源汇上下界可行流
从 $T$ 到 $S$ 连一条下界为 $0$，上界为 $+\infty$ 的边，把汇流入的流量转移给源流出的流量，转化为无源汇的网络，然后求解**无源汇上下界可行流**。
#### 有源汇上下界最大流
##### 【模板】[LOJ116 有源汇有上下界最大流](https://loj.ac/problem/116)
两个方法：
1. 二分答案 $ans$，从 $T$ 到 $S$ 连一条下界为 $ans$，上界为 $+\infty$ 的边，转化为无源汇网络。找到最大的 $ans$，使得该无源汇上下界网络有可行流。
2. 从 $T$ 到 $S$ 连一条下界为 $0$，上界为 $+\infty$ 的边，转化为无源汇网络。按照**无源汇上下界可行流**的做法求一次无源汇上下界超级源到超级汇的最大流。回到原网络，在上一步的**残量网络**基础上，求一次 $S$ 到 $T$ 的最大流。以下代码采用此方法。
```cpp
namespace yes_max_flow {
const ll inf = 1e18;
int n, S, T;
inline bool main() {
no_ok_flow::add(T, S, 0, inf);
if (!no_ok_flow::main()) return 0;
Dinic::S = S, Dinic::T = T, Dinic::mxf = 0;
return Dinic::main(), 1;
}
inline void init(int _n, int _S, int _T) {
n = _n, S = _S, T = _T;
no_ok_flow::init(n);
}
}
int main() {
int n, m, S, T;
rd(n), rd(m), rd(S), rd(T);
yes_max_flow::init(n, S, T);
for (int i = 1, x, y, l, r; i <= m; i++)
rd(x), rd(y), rd(l), rd(r), no_ok_flow::add(x, y, l, r);
if (!yes_max_flow::main()) return prints("please go home to sleep"), 0;
print(Dinic::mxf);
return 0;
}
```
#### 有源汇上下界最小流
##### 【模板】[LOJ117 有源汇有上下界最小流](https://loj.ac/problem/117)
同样两个方法：
1. 二分答案 $ans$，从 $T$ 到 $S$ 连一条下界为 $0$，上界为 $ans$ 的边，转化为无源汇网络。找到最小的 $ans$，使得该无源汇上下界网络有可行流。
2. 类似**有源汇上下界可行流**的构图方法，但先不添加 $T$ 到 $S$ 的边，求一次超级源到超级汇的最大流。然后再添加一条从 $T$ 到 $S$ 下界为 $0$，上界为 $+\infty$ 的边，在**残量网络**上再求一次超级源到超级汇的最大流，流经 $T$ 到 $S$ 的边的流量就是最小流的值。该算法的思想是在第一步中尽可能填充循环流，以减小最小流的代价。以下代码采用此方法。
```cpp
namespace yes_min_flow {
const ll inf = 1e18;
int n, S, T;
inline bool main() {
no_ok_flow::main();
no_ok_flow::add(T, S, 0, inf);
Dinic::main();
return Dinic::mxf == no_ok_flow::s;
}
inline void init(int _n, int _S, int _T) {
n = _n, S = _S, T = _T;
no_ok_flow::init(n);
}
}
int main() {
int n, m, S, T;
rd(n), rd(m), rd(S), rd(T);
yes_min_flow::init(n, S, T);
for (int i = 1, x, y, l, r; i <= m; i++)
rd(x), rd(y), rd(l), rd(r), no_ok_flow::add(x, y, l, r);
if (!yes_min_flow::main()) return prints("please go home to sleep"), 0;
print(Dinic::f[Dinic::tot]);
return 0;
}
```
##### 【例题】[P4843 清理雪道](https://www.luogu.com.cn/problem/P4843)
> DAG 的最小**边**覆盖。
连边：
1. $(S,i,0,+\infty)$。
2. $(i,T,0,+\infty)$。
3. 对每条斜坡 $(i,j)$，连边 $(i,j,1,+\infty)$。
求**有源汇上下界最小流**即可。
#### 上下界最小费用可行流
类似**上下界可行流**，求最大流改为求最小费用最大流。
##### 【例题】[P4553 80人环游世界](https://www.luogu.com.cn/problem/P4553)
> 有 $n$ 个国家，$m$ 个人。
> 第 $i$ 个国家必须有 $v_i$ 个人经过，不能多也不能少。
> 对于 $i,j(i < j)$，$i \to j$ 有一条费用为 $c_{i,j}$ 的边（若 $c_{i,j}=-1$ 则表示没有边）。
> 求最小费用。
第 $i$ 个国家拆成两个点（入点 $i$ 和出点 $i+n$），建立源 $S$ 汇 $T$ 附加源 $s$
连边：
1. $(S,s,m,m,0)$。
2. $(s,i,0,m,0)$。
3. $(i+n,T,0,m,0)$。
4. $(i,i+n,v_i,v_i,0)$。
5. 若 $i,j$ 两个国家之间有边，连边 $(i+n,j,0,m,c_{i,j})$。
求**有源汇上下界最小费用可行流**即可。
```cpp
namespace no_min_cost_flow {
const int N = 1e5 + 7;
int n, S, T;
ll d[N], s;
inline void add(int x, int y, ll l, ll r, ll w) {
EK::add(x, y, r - l, w), d[y] += l, d[x] -= l;
}
inline bool main() {
for (int i = 1; i <= n; i++)
if (d[i] > 0) EK::add(S, i, d[i], 0), s += d[i];
else if (d[i] < 0) EK::add(i, T, -d[i], 0);
EK::main();
return EK::mxf == s;
}
inline void init(int _n) {
n = _n, s = 0, S = n + 1, T = n + 2;
EK::init(n + 2, S, T);
for (int i = 1; i <= n; i++) d[i] = 0;
}
}
const ll inf = 1e18;
int main() {
int n, m, S, T, s;
rd(n), rd(m), s = 2 * n + 1, S = 2 * n + 2, T = 2 * n + 3;
no_min_cost_flow::init(2 * n + 3);
no_min_cost_flow::add(T, S, 0, inf, 0);
no_min_cost_flow::add(S, s, m, m, 0);
for (int i = 1, x; i <= n; i++)
no_min_cost_flow::add(s, i, 0, m, 0), no_min_cost_flow::add(i + n, T, 0, m, 0),
rd(x), no_min_cost_flow::add(i, i + n, x, x, 0);
for (int i = 1, x; i <= n; i++)
for (int j = i + 1; j <= n; j++) {
rd(x);
if (~x) no_min_cost_flow::add(i + n, j, 0, m, x);
}
no_min_cost_flow::main();
print(EK::ans);
return 0;
}
```
##### 【例题】[P3980 [NOI2008]志愿者招募](https://www.luogu.com.cn/problem/P3980)
> 有一个项目需要 $n$ 天完成，第 $i$ 天至少需要 $a_i$ 个人。
> 有 $m$ 类志愿者，第 $i$ 类可以从第 $s_i$ 天工作到第 $t_i$ 天，费用为每人 $c_i$ 元。
> 求最小费用。
把每一天看作一个点。
连边：
1. $(i,i+1,a_i,+\infty,0)$。
2. $(t_i +1, s_i, 0, +\infty, c_i)$。
在这个无源汇网络中，招募一个第 $i$ 类志愿者，就会产生一个从 $s_i$ 到 $t_i+1$ 的环流，并且使花费加 $c_i$。
这与题目的实际意义正好相对应，在这个网络中求**无源汇上下界最小费用可行流**即可。
### 最大权闭合子图
若有向图 $G$ 的子图 $V$ 满足：$V$ 中顶点的所有出边均指向 $V$ 内部的顶点，则称 $V$ 是 $G$ 的一个**闭合子图**。
若 $G$ 中的点有点权，则**点权和最大**的闭合子图称为有向图 $G$ 的**最大权闭合子图**。
#### 构图方法
建立源点 $S$ 和汇点 $T$ ，源点 $S$ 连所有点权为正的点，容量为该点点权；其余点连汇点 $T$，容量为该点点权的相反数，对于原图中的边 $(x,y)$，连边 $(x,y,+\infty)$。
#### 定理
- **最大权闭合图的点权和**等于**所有正权点权值和**减去**最小割**。
- 上述图的最小割包含 $S$ 到**不在最大权闭合图内的正权节点**的边和**在最大权闭合图内的负权节点**到 $T$ 的边。
#### 推论（最大权闭合图方案）
在**残量网络**中由源点 $S$ 能够访问到的点，就构成一个**点数最少**的最大权闭合子图。
##### 【例题】[P2805 [NOI2009]植物大战僵尸](https://www.luogu.com.cn/problem/P2805)
> 每个植物都携带了一些能源（可以是负数），某些植物可以保护其它植物。
> 一个植物可以被吃掉，当且仅当所有保护它的植物都被吃掉了。
> 僵尸要吃掉一些植物，使得获得的能源最大。
把每个植物当做一个顶点，植物携带的能源为顶点的权值。
如果植物 $b$ 在植物 $a$ 的攻击范围内，连接一条有向边 $(a,b)$，表示 $a$ 可以保护 $b$。
由于僵尸从右向左进攻，可以认为每个植物都被它右边相邻的植物保护，对于每个植物 $a$（除最左边一列），向其左边的相邻植物 $b$，连接一条有向边 $(a,b)$。
**此时可能有一些植物是互相保护的，都不能被吃掉，这样的点（和与其相连的边）应该全部删掉，拓扑排序一遍即可。**
如果我们将图**转置**（即所有边转成其反向边），那么可以吃掉的植物应该构成一个闭合子图，而最优解就是最大权闭合子图。
## 致谢 & 参考资料
本文中大量的内容来自 PKU 的李煜东老师，包括他编写的《算法竞赛进阶指南》中的内容，以及他提供的《二分图与网络流模型设计》课件。**特别说明：这些引用均经过了李煜东老师的授权，任何人在未经过我和李煜东老师的授权下禁止引用本文中的任何内容。**