网络流与匹配

网络流把"容量约束下的运输"形式化：边上限流，求源到汇的最大流量。它的威力在于建模——很多看似无关的问题（匹配、切割、调度）都能归约到流。本章讲主流算法、最大流最小割定理与匹配。

问题与建模

流网络：有向图，每条边有容量 $c(e)$ ，源 $s$ 、汇 $t$ 。流满足两条：容量约束（ $0 \le f(e) \le c(e)$ ）与守恒（除源汇，进 = 出）。求 $s \to t$ 的最大流量。

残余网络：剩余容量 $c - f$ 加反向边 $f$ ——反向边是所有流算法的关键：它允许"撤销"之前的流，把次优分配改掉。没有反向边，贪心会卡在次优解。

反复在残余网络中找增广路径（ $s \to t$ 的正容量路径），沿路径推流。整数容量时终止，但找路径的方式决定复杂度：任意路径最坏 $O(E \cdot |f_{\max}|)$ （慢），按容量最大或最短路径选择则多项式。

增广路径取 BFS（边数最少）。复杂度 $O(VE^2)$ ——增广次数有界 $O(VE)$ ，与容量无关。实现最简单的多项式流算法。

分层网络（按到源的距离分层）+ 阻塞流（一次 DFS 推尽可能多的流）：阶段数 $O(V)$ ，每阶段 $O(VE)$ ，总 $O(V^2E)$ ；单位容量图上 $O(E\sqrt{E})$ 。实践中通常最快，是竞赛与工程的主流。

最小割：把顶点分成含 $s$ 与含 $t$ 的两部分，横跨的容量之和；最小的那个是"最窄的瓶颈"。定理：

\max_{f} |f| = \min_{(S, T)} \sum_{e \in S \to T} c(e).

证明思路：最大流时残余网络无增广路 → 可达集即最小割。最大流 = 最小割是线性规划对偶的特例——原始问题（流）与对偶问题（割）的值相等，这是 LP 对偶最直观的实例。推论与应用：对偶性、图的连通性（边连通度 = 最小割）、图像分割（前景/背景切割）。

匈牙利算法求二分图最大匹配：反复找增广路径（交替未匹配/匹配边的路径），找到则翻转增配。 $O(VE)$ 。

更简单的建模：二分图匹配可用最大流解——源连左侧（容量 1），左右之间边容量 1，右侧连汇（容量 1），最大流即最大匹配。最小点覆盖 = 最大匹配（König 定理）也是对偶性的实例。

建图能力比算法本身更重要。常见的归约模式：

判断信号：问题里有"容量/上限"、有"配对/分配"、有"分割/选择"——先想流。