返回：0400 算法设计与分析总目录 · 上一章：0406 Chap6 动态规划 · 下一章：0408 Chap8 NP 与计算困难性

1、学习目标

网络流用图来描述“从源点向汇点运输资源”的问题。它看起来像运输问题，实际能统一解决匹配、割、任务分配、项目选择等很多模型。

模块 要掌握的内容
流网络 源点、汇点、容量、流量
约束 容量约束、流量守恒
残量网络 还能增广多少，能否反悔
算法 Ford-Fulkerson、Edmonds-Karp
定理 最大流最小割
应用 二分图匹配

2、流网络

一个流网络包含：

1
2
3
4
G = (V, E)
s = source
t = sink
c(e) = capacity

合法流 f 满足：

约束 含义
容量约束 0 <= f(e) <= c(e)
流量守恒 除 s、t 外，流入等于流出
流值 从源点流出的总量，等于流入汇点的总量

3、割

一个 s-t 割把顶点分成两组：

1
2
3
4
S 包含 s
T 包含 t
S ∪ T = V
S ∩ T = 空

割容量是所有从 S 指向 T 的边容量之和。

重要事实：

1
任意流的流值 <= 任意 s-t 割的容量

所以最小割容量是最大流的上界。

4、残量网络

残量网络描述在当前流的基础上还能怎么调整。

对一条边 u -> v：

  1. 正向残量：还能继续增加多少流，c(u,v)-f(u,v)。
  2. 反向残量：可以撤回多少已有流，f(u,v)。

反向边很关键，它表示算法可以“反悔”。没有反向边，早期不好的选择可能堵死后续路径。

5、Ford-Fulkerson

算法框架：

1
2
3
4
初始化所有边流量为 0
while 残量网络中存在 s 到 t 的路径 P:
    找到 P 上最小残量 bottleneck
    沿 P 增广 bottleneck

伪代码：

1
2
3
4
5
6
while (findAugmentingPath(s, t, parent)) {
    int aug = INF;
    for (edge e on path) aug = min(aug, residual(e));
    for (edge e on path) augment(e, aug);
    maxflow += aug;
}

如果容量是整数，每次至少增加 1，算法会终止。但随意选择增广路时，复杂度可能依赖最大流值。

6、Edmonds-Karp

Edmonds-Karp 是 Ford-Fulkerson 的一个具体实现：

1
每次用 BFS 找边数最少的增广路。

复杂度：

1
O(V E^2)

虽然不是最快的最大流算法，但它概念清楚，非常适合入门。

7、最大流最小割定理

定理：

1
最大 s-t 流值 = 最小 s-t 割容量

证明直觉：

  1. 任意流都不超过任意割，所以最大流 <= 最小割。
  2. 当残量网络中不存在增广路时，从 s 可达的点集记为 S。
  3. 此时所有从 S 到 T 的边都已满，所有从 T 到 S 的边流量为 0。
  4. 当前流值等于这个割的容量。
  5. 因此当前流就是最大流，这个割就是最小割。

这条定理是网络流里最重要的结构性结论。

8、二分图匹配

二分图最大匹配可以转化成最大流：

  1. 新增源点 s 和汇点 t。
  2. s 连到左部每个点，容量为 1。
  3. 左部点连到右部点，容量为 1。
  4. 右部每个点连到 t，容量为 1。

最大流值就是最大匹配数。

1
s -> left -> right -> t

容量为 1 保证每个点最多匹配一次。

9、建模套路

问题特征 建模方式
资源从一端流到另一端 源点、汇点、容量边
每个对象最多用一次 容量设为 1
选择与不选择 拆点或连源汇
最小割惩罚 把代价放在割边容量上
二分关系 左右部 + 容量 1

网络流建模的难点不是代码，而是把约束变成容量和守恒。

10、复杂度汇总

算法 复杂度 说明
Ford-Fulkerson O(E * maxflow) 整数容量且增广路任意
Edmonds-Karp O(VE^2) BFS 找最短增广路
二分图匹配转最大流 取决于最大流算法 容量多为 1

11、易错点

易错点 修正
忘记反向边 残量网络必须支持撤回
把最短路和增广路混淆 增广路只要求残量为正
割容量算双向边 只算从 S 到 T 的边
二分图匹配容量设大 容量 1 才能限制每点匹配一次
只记算法不记定理 最大流最小割是核心

12、复盘清单

检查项 状态
能定义合法流和流值 待复盘
能解释残量网络的反向边 待复盘
能手动跑一轮 Ford-Fulkerson 待复盘
能证明无增广路时得到最小割 待复盘
能把二分图匹配转成最大流 待复盘