一、流网络
流网络：有向图 G = (V, E)，每条边有容量
c(u,v) ≥ 0，指定源点 s 与汇点 t。流 f 是一个函数，满足：
- 容量约束：
0 ≤ f(u,v) ≤ c(u,v)- 流守恒：对每个
v ≠ s, t，Σ 流入 = Σ 流出流的值
|f| = 从 s 流出的净流量。最大流问题：求 |f| 最大的流。
┌─12─▶ v₁ ──20──▶ v₃ ─┐
16│ │ ╲ │ 4
s ──┘ 4 9 └──▶ t
13│ ▼ ╲ 7 ▲
└────▶ v₂ ────────▶ v₄ ─┘
14
直觉模型：水管网络、公路运力、网络带宽。但网络流真正的威力在于它能建模大量看起来毫不相关的问题——这是本讲的重点。
二、残量网络与增广路
残量网络
给定流 f，残量容量 定义为：
c_f(u,v) = c(u,v) − f(u,v) 正向：还能推多少
c_f(v,u) = f(u,v) ⭐ 反向：可以"撤销"多少
⭐ 反向边是全部的关键。 它让算法可以"后悔"——如果之前的选择不好，后面的增广路可以通过反向边把流"退回来"，重新路由。
容量 10，已流 6：
正向残量 4： u ──4──▶ v 还能再推 4
反向残量 6： u ◀──6─── v 可以退回 6
没有反向边的贪心是错的：
s ──1──▶ a ──1──▶ t
│ │ ▲
1 1 1
│ ▼ │
└─────▶ b ──────┘
五条边容量全是 1：s→a、s→b、a→b、a→t、b→t
真正的最大流 = 2（走 s→a→t 与 s→b→t）
❌ 无反向边：若先选中 s→a→b→t（推 1），则 s→a、a→b、b→t 全部饱和。
此后从 s 只能走 s→b，而 b 的唯一出边 b→t 已满 ⟹ 卡死，只得到 1。
✓ 有反向边：第二条增广路 s→b→(沿 a→b 的反向边退回)→a→t 再推 1 ⟹ 总流 2。
这一步的实际效果是「把原先经 a→b 的那一单位改道成 a→t」。
增广路
增广路：残量网络中一条从 s 到 t 的路径。沿它推流量 = 路径上最小残量容量。
type FlowEdge struct {
To, Rev int // Rev 是反向边在 adj[To] 中的下标
Cap int
}
type FlowNetwork struct {
n int
adj [][]FlowEdge
}
func (g *FlowNetwork) AddEdge(u, v, cap int) {
g.adj[u] = append(g.adj[u], FlowEdge{To: v, Rev: len(g.adj[v]), Cap: cap})
g.adj[v] = append(g.adj[v], FlowEdge{To: u, Rev: len(g.adj[u]) - 1, Cap: 0}) // 反向边初始容量 0
}
⭐ “成对存边"的技巧：正反两条边相邻存放，推流时 Cap -= d 同时 反向边.Cap += d。这是网络流实现的标准写法。
三、最大流最小割定理
割 (S, T)：把顶点分成两部分，s ∈ S，t ∈ T。 割的容量
c(S,T) = Σ_{u∈S, v∈T} c(u,v)（只算从 S 到 T 的边）。 最小割：容量最小的割。
引理（弱对偶）：任意流的值 ≤ 任意割的容量。
证明：所有从 s 到 t 的流量都必须跨过这个割，而跨割的容量上限就是 c(S,T)。∎
⭐ 最大流最小割定理（Ford-Fulkerson, 1956）
以下三个命题等价：
- f 是最大流
- 残量网络中不存在增广路
- 存在某个割 (S,T) 使得
|f| = c(S,T)因此：最大流的值 = 最小割的容量。
证明（循环论证 1⟹2⟹3⟹1）：
(1 ⟹ 2)：若有增广路，就能增大流，与最大性矛盾。
(2 ⟹ 3)：设 S = 残量网络中从 s 可达的所有顶点，T = V − S。因为无增广路，t ∉ S，所以 (S,T) 是一个合法的割。对任意 u ∈ S、v ∈ T：
- 边 (u,v) 必然满流（
f(u,v) = c(u,v)），否则残量 > 0，v 就可达了 - 边 (v,u) 必然零流（
f(v,u) = 0），否则反向残量 > 0，v 也可达
因此 |f| = c(S,T)。
(3 ⟹ 1)：由弱对偶，|f| ≤ 任意割。既然 |f| = c(S,T)，f 达到了上界，必是最大流。∎
⭐ 这是组合优化中最优美的定理之一，也是「线性规划对偶性」在图论中的具体化身。它把一个最大化问题和一个最小化问题绑在了一起。
求最小割：跑完最大流后，残量网络中从 s 可达的顶点集合就是 S，割边就是从 S 指向 T 的原图边。
四、算法
Edmonds-Karp：用 BFS 找增广路
func (g *FlowNetwork) MaxFlow(s, t int) int {
flow := 0
for {
// BFS 找最短增广路（边数最少）
parent := make([]int, g.n) // parent[v] = 到达 v 的边在 adj[u] 中的下标
pv := make([]int, g.n) // pv[v] = 前驱顶点
for i := range parent { pv[i] = -1 }
pv[s] = s
queue := []int{s}
for len(queue) > 0 && pv[t] == -1 {
u := queue[0]
queue = queue[1:]
for i, e := range g.adj[u] {
if e.Cap > 0 && pv[e.To] == -1 {
pv[e.To], parent[e.To] = u, i
queue = append(queue, e.To)
}
}
}
if pv[t] == -1 {
return flow // 无增广路，结束
}
// 找瓶颈
bottleneck := math.MaxInt
for v := t; v != s; v = pv[v] {
bottleneck = min(bottleneck, g.adj[pv[v]][parent[v]].Cap)
}
// 沿路径推流
for v := t; v != s; v = pv[v] {
e := &g.adj[pv[v]][parent[v]]
e.Cap -= bottleneck
g.adj[v][e.Rev].Cap += bottleneck // ⭐ 反向边加上
}
flow += bottleneck
}
}
复杂度 O(V·E²)。
为什么用 BFS 而不是 DFS？
⚠️ 朴素 Ford-Fulkerson（DFS 任意找增广路）在容量是无理数时可能不终止，在整数容量下复杂度是 O(E · |f|)*——与流值有关，不是多项式：
C C
s ────────▶ a ────────▶ t
│ │ ▲
│C 1│ │C
│ ▼ │
└────────▶ b ──────────┘
C = 1 000 000，唯独中间那条 a→b 的容量是 1
最大流 = 2C = 2×10⁶（走 s→a→t 与 s→b→t，各 C）
若每次都挑中长度为 3 的那条路：
第 1 次 s→a→b→t 推 1（a→b 饱和）
第 2 次 s→b→(反向)a→t 推 1（a→b 退回 0）
两条交替往复……每次只推进 1 单位 ⟹ 共需 2×10⁶ 次增广
而 BFS 只挑长度为 2 的最短路，2 次增广（各 C）就结束了。
Edmonds-Karp 用 BFS 选最短增广路，可以证明增广次数是 O(V·E)，与容量无关，得到 O(V·E²)。这是"选择顺序影响复杂度"的经典案例。
Dinic 算法
两个优化叠加：
- 分层图（level graph）：BFS 给每个顶点标记到 s 的层数，只允许走
level[v] = level[u] + 1的边。 - 阻塞流（blocking flow）：在分层图上用 DFS 一次找出多条增广路，直到没有 s→t 的路。
- 当前弧优化：记录每个顶点已经尝试到第几条边，避免重复扫描死路。
复杂度：O(V² · E) 一般图
O(E · √V) ⭐ 单位容量图（如二分匹配）
O(V^(2/3) · E) 单位容量且无重边
⭐ Dinic 是实践中的标准选择：实现难度中等，实测远快于 Edmonds-Karp，在多数场景下表现接近线性。竞赛和工程中"网络流"基本就是指 Dinic。
五、二分匹配
这是网络流最重要的应用，也是最能体现"归约"威力的例子。
二分图最大匹配：二分图 G = (L ∪ R, E)，求最大的边集 M，使 M 中任意两条边不共享顶点。
归约成最大流：
┌──1──▶ l₁ ──▶ r₁ ──1──┐
│ ╲ ╱ │
s ───┼──1──▶ l₂ ─╳─ r₂ ──1───┼──▶ t
│ ╱ ╲ │
└──1──▶ l₃ ──▶ r₃ ──1──┘
① s 向每个左顶点连容量 1 的边
② 原图的每条边 (l,r) 连容量 1（或 ∞）
③ 每个右顶点向 t 连容量 1 的边
⟹ 最大流的值 = 最大匹配的大小
为什么对？ 容量 1 保证每个顶点最多被用一次（对应匹配的定义），流的整数性定理保证最大流可以取到整数值，每条流量为 1 的路径对应一条匹配边。
复杂度：Dinic 在单位容量图上是 O(E√V)，这也是 Hopcroft-Karp 算法的复杂度（后者是专门为二分匹配设计的，本质是同一个思路）。
⚠️ 简单实现可以用 匈牙利算法（对每个左顶点找增广路），O(V·E)，代码只有 20 行，小规模问题足够。
⭐ König 定理与三个等价问题
König 定理（二分图）：最大匹配数 = 最小顶点覆盖数。
最小顶点覆盖：选最少的顶点，使每条边至少有一个端点被选中。
由此还能推出（设二分图有 n 个顶点）：
最大独立集 = n − 最大匹配
最小路径覆盖（DAG）= n − 拆点二分图的最大匹配
最小边覆盖 = n − 最大匹配 （无孤立点时）
⭐ 这组等价关系的实用价值极大：很多问题表面上是"选最多互不冲突的东西”（独立集）或"用最少的东西覆盖全部"（覆盖），在二分结构下它们都归结为一次最大匹配。
⚠️ 注意"二分"这个前提：一般图的最大独立集和最小顶点覆盖都是 NP-完全的（第 34 讲）。二分结构是让它们变简单的唯一原因。
六、建模：把问题变成流
网络流的真正难点不是算法（照抄 Dinic 即可），而是建图。
| 问题 | 建模方式 |
|---|---|
| 二分匹配 | s→左，左→右，右→t，容量全 1 |
| 多源多汇 | 加超级源 S 连所有源、超级汇 T 连所有汇 |
| 顶点容量限制 | ⭐ 拆点：v 拆成 v_in → v_out，中间边容量 = 顶点容量 |
| 最小割 = 二元选择 | 每个物品要么归 S 要么归 T，割边代价 = 分开的代价 |
| 项目选择（最大权闭合子图） | 正收益点连 s，负收益点连 t，依赖关系连 ∞ 边；答案 = 正收益和 − 最小割 |
| 最小路径覆盖（DAG） | 每个点拆成出点和入点，做二分匹配 |
| 有上下界的流 | 转化成无上下界的可行流问题 |
| 最小费用最大流 | 每条边加费用，用 Bellman-Ford/SPFA 找最短增广路 |
⭐ “拆点"和"最小割 = 二元划分"是两个最常用的建模技巧。特别是后者：
当一个问题的形式是"每个元素必须二选一，某些组合会产生代价"时，往往可以建成最小割。 图像分割（前景/背景）、项目选择（做/不做）、任务分配（机器 A / 机器 B）都是这个模式。
七、复杂度汇总
| 算法 | 复杂度 | 备注 |
|---|---|---|
| Ford-Fulkerson (DFS) | O(E·|f*|) | ⚠️ 非多项式，可能不终止 |
| Edmonds-Karp | O(V·E²) | BFS 找最短增广路 |
| Dinic | O(V²·E) | 实践首选 |
| Dinic（单位容量） | O(E√V) | 二分匹配 |
| Push-Relabel | O(V³) 或 O(V²√E) | 理论快，实现复杂 |
| 匈牙利算法（二分匹配） | O(V·E) | 代码最短 |
| Hopcroft-Karp | O(E√V) | 二分匹配专用 |
| 最小费用最大流（SPFA） | O(V·E·f) | 每轮找最短路增广 |
随堂自测
- 流必须满足哪两个约束？流的值如何定义？
- 残量网络中的反向边有什么作用？给出一个"没有反向边就得不到最优解"的例子。
- 陈述最大流最小割定理的三个等价命题，并完成 (2 ⟹ 3) 的证明。
- 跑完最大流后，如何在 O(V+E) 内找出最小割的具体边集？
- 为什么朴素 Ford-Fulkerson 的复杂度 O(E·|f*|) 不算多项式？构造一个使它需要百万次增广的图。
- Edmonds-Karp 用 BFS 而非 DFS，为什么这一个改动就把复杂度变成了多项式？
- Dinic 的两个核心优化是什么？为什么它在单位容量图上是 O(E√V)？
- 把二分图最大匹配归约成最大流，说明容量设为 1 保证了什么。
- 陈述 König 定理，并写出最大独立集与最大匹配的关系。为什么这个关系只对二分图成立？
- 什么是"拆点"技巧？它解决什么建模需求？
- 什么样的问题适合建模成最小割？给出一个例子。