在 ACM 中第一次听到网络流，但是还没认真学就被迫退 役了。（菜的真实）

第二次是在肖老师的 算法设计与分析 课程上，大概了解了网络流的思想。

本文参考《算法设计》，对网络流的研究偏向理论，会涉及到一些证明。

定义

流网络

流网络（flow network）是一种带权有向图，但是有一个源点（source）和一个汇点（sink），每个权叫做该边的容量（capacity）$c(e)$。如下图。

对流网络我们有三点假设：

1. 没有边进入 $s$ 点，没有点离开 $t$ 点
2. 所有结点至少在一条边上
3. 所有的容量都为整数（这点很重要，是 Ford-Fulkerson 算法会结束的前提）

流

流是一个比较形象的概念，好比每个有向边都是一根管道，权重代表这根管道能流多少水。

但是要想用数学定义下来，还是比较麻烦。

$s-t$ 流是一个满足以下条件的函数：

1. 对于图中任意一边 $e$，有 $0 \leq f(e) \leq c(e)$
2. 对于图中任意一点 $v$，有 $\sum_\text{e in to v}f(e) = \sum_\text{e out of v}f(e)$

这里是把每一种流法定义为了不同的函数 $f$，用这个函数作用于每一条 $e$ 即可查看这种流法里“管道” $e$ 里流经了多少水。

流的价值： $v(f) = \sum_\text{e out of s}f(e)$。

最大流即为最大价值的流。

下图的一个流为 24。（但最大流为 28，从上往下流进 $t$ 点的流量为 9、9、10，请读者自己思考这是如何达到的）

割

然后我们要引入：

$s-t$ 割，就是把图分为 $A$、$B$ 两块的一种方法，要满足 $A$ 块有 $s$，$B$ 块有 $t$。

并定义 A-B 割的容量为流出 $A$ 块的所有容量之和：

$cap(A, B) = \sum_\text{e out of A} c(e)$

最小割即指容量最小的割。

最大流-最小割定理

接下来我们想要证明最大流-最小割定理：

在每个流网络中，一个图中，一个 s-t 流的最大值等于一个 s-t 割的最小容量。

首先我们证明引理：

$\sum_\text{e out of A} {f(e)} - \sum_\text{e in to A} {f(e)} = v(f)$

这里的 "out of" 和 "in to" 指的是穿出、穿进 $A$ 块的单向边。

证明：

$\begin{aligned} v(f) &= \sum_\text{e out of s}f(e) & \text{(流的定义)} \\ &= \sum_{v \in A}\bigg(\sum_\text{e out of v}f(e) - \sum_\text{e in to v}f(e)\bigg) \qquad & \text{(加了一堆为值 0 的表达式)} \\ &= \sum_\text{e out of A}f(e) - \sum_\text{e in to A}f(e) & \text{(证明见后)}\\ \end{aligned}$

第三行的证明需要讨论几种情况的边：

• 如果某边 $e$ 的两个点都在 $A$ 内，这条边在第二行的贡献为一正一负，抵消为零；
• 如果某边 $e$ 穿出了 A（即入点在 $A$ 内，出点在 $B$ 内），这条边在第二行的贡献为一次正值；
• 如果某边 $e$ 穿入了 A（即入点在 $B$ 内，出点在 $A$ 内），这条边在第二行的贡献为一次负值。

综上讨论和 "out of" "in to" 的定义可得第三行的正确性。

由上面的结果，我们可以继续往下推得：对于某个图中的任意流 $f$ 和任意 $(A,B)$ 割，有：

$v(f) \leq cap(A,B)$

证明：

$\begin{aligned} v(f) &= \sum_\text{e out of A}f(e) - \sum_\text{e in to A}f(e) \\ &\leq \sum_\text{e out of A}f(e) \\ &\leq \sum_\text{e out of A}c(e) \\ &=cap(A,B). \end{aligned}$

那么显然地，对于一个流网络，如果找到一个流 $f$ 和 $cap(A,B)$，有 $v(f)=cap(A,B)$，那么 $f$ 就一定是最大流，且 $(A,B)$ 一定是最小割。

到这里，貌似还没有证明最大流等于最小割，因为我们不知道是不是一定存在一个流和割，满足 $v(f)=cap(A,B)$。
我们后面会提到 Ford-Fulkerson 算法，对于这个算法返回的流，我们可以构造一个 $s-t$ 割使得该割等于算法返回的流，即完成了证明。

最大流算法

贪心算法

最容易想到的是先用贪心跑一下。贪心算法如下：

1. 刚开始设所有边的 $f(e)=0$；
2. 找到任意一条从 $s$ 连向 $t$，且每条边都还没有流满（即 $f(e) < c(e)$）的路径 P。增大该路径每条边上的流；
3. 反复执行上步操作直到流不动了。

贪心在一些图上确实有很好的表现，但是很容易构造出贪心不是最优解的情况，如下：

造成这个的问题是，可能会先选到一条不好的边，导致某个瓶颈满了，其他边无法继续流。

于是就想到了一种可以把已经被占满的边撤销、改回来的方法，叫剩余图(Residual graph)。

剩余图

根据之前的设定，原图中的每一条边 $e$ 都有 $c(e)$ 和 $f(e)$。

对于原图的每一条边，我们在一个新的图中都定义两条相互反向的边，把他命名叫剩余边（Residual edge）。

定义剩余边的权重（剩余容量，Residual capacity）：我们把与原图的边同向的边的剩余容量设为原边还能流的量 $c(e)-f(e)$，把反向的边设为原边已经流过的量 $f(e)$。

$c_f(e)=\begin{cases} c(e) - f(e) & {\rm if} \quad e \in E \\ f(e) & {\rm if} \quad e^R \in E \end{cases}$

刚才的新图便叫做剩余图（又叫残余网络，Residual graph）。

Ford-Fulkerson 算法

良心的肖老师也提供了演示 PPT。

Ford-Fulkerson 的算法即是先建立剩余图，然后在剩余图上进行我们最开始的贪心。

在增大每边的流量时，需要减少同向边的容量，同时增加反向边的容量。

这样做的好处，就是当有一条边被正向流满，导致图中好像没有可以增加流时，此时可以使用这条边的反向边进行增加流。

如 贪心算法 提到的图中，上到下的边被流满了，如果此时开放下到上的边，就可以增加 10 的流量，即达到最大流。顺便一提，“开放一条边”这个过程被称作 “增广路”（Augmenting path）。

下面是 Ford-Fulkerson 算法的伪代码。

算法的正确性证明分为两个部分：一要证明算法会终止；二要证明算法返回的流为最大流。

算法终止的证明如下：

显然，在所有 $c(e)$ 都是整数的前提下，算法每一个步骤中的 $f(e)$ 和增广（Augment）值都一定为整数。

而每次的增广值一定大于 0，故每次增广，流的值会增长至少 1。

显然流的值不可能无限大（一个显然的上界就是 $\sum_\text{e out of s}c(e)$），因此算法必然会停止。

算法返回的流为最大流的证明放在下面。

最大流-最小割定理证明

作个铺垫，由 Ford-Fulkerson 算法的终止条件，显然有：如果算法终止，算法返回的流不存在增广路了。

接下来我们要证明两点：一是不存在增广路的流是最大流；二是最大流等于最小割。

证明的方式是证明以下三个命题等价：

(i) 存在割 $(A,B)$ 使得 $cap(A,B)=v(f)$
(ii) 流 $f$ 是最大流
(iii) 流 $f$ 不存在增广路

(i) -> (ii) 由前面的引理可得。

(ii) -> (iii) 反证：如果 $f$ 还存在增广路，按照 Ford-Fulkerson 的算法跑一下就可以使流的值变大，与最大流的前提矛盾。

(iii) -> (i) 设 $A$ 为在最后的剩余图从源点 $s$ 出发能到达的所有点的集合，$B=V-A$。

显然 $(A,B)$ 为原图的一个割，且有：

$\begin{aligned} v(f) &= \sum_\text{e out of A}f(e) - \sum_\text{e in to A} f(e) & \text{(由前面的引理)} \\ &= \sum_\text{e out of A}c(e) & \text{(证明见后)} \\ &= cap(A,B) & \text{(割容量的定义)} \end{aligned}$

第二行的证明： 对于 $e$ out of A，一定有 $f(e)=c(e)$，否则：

$e$ 在剩余图中仍然存在。
设 $e=(u,v)$，由 "out of" 的定义， $u \in A$，$v \notin A$。 由 $A$ 的假设，在剩余图中 $s$ 到 $u$ 存在通路。 将该通路与 $e$ 拼接，则 $s$ 到 $v$ 也有通路，与 $v \notin A$ 矛盾。

同理，对于 $e$ in to A，一定有$f(e)=0$，否则 $e^R$ 将存在于剩余图。

证明完毕。算法的正确性也同时被证明了。

时间复杂度

设图中点数为 $n$，边的数量为 $m$，边的最大容量为 $C$。

由于假设所有点都在至少一条边上，有 $n \leq 2m$，即 $O(n + m) = O(m)$。

Ford-Fulkerson 算法会停止的证明中，我们证明了

• $v(f)$ 有一个上界为 $\sum_\text{e out of s}c(e)$，也就是 $O(mC)$；
• 算法每次迭代必定增长 1。

而每一次迭代的复杂度显然可以在 $O(m)$ 之内完成。

因此，Ford-Fulkerson 算法的时间复杂度为 $O(m^2 C)$。

但是，这个算法不是多项式时间复杂度的！！！！这个算法是伪多项式时间复杂度的。原因是 $C$ 对于输入规模是指数级的。而如果选择增广路的方法不恰当，我们构造出下图，迭代次数确实可以达到 $\Theta(C)$ 次。

缩放最大流算法

问题就在于，每次选择了瓶颈（bottleneck）最小的边进行增广。能不能选择最大的边呢？于是就有了缩放最大流（Scaling Max-Flow）算法。

我们维护一个 $\Delta$，迭代过程中让 $\Delta$ 由大到小。每次增广时只考虑大于 $\Delta$ 的边。下面上代码：

Dinitz、Edmonds 和 Karp 分别独立证明了增广路算法能够在

后记

最大流问题中还有一个经典的问题: 最小吧 费用最大流问题。请大家自学。 对于求最大流的算法, 在实践中往往使用效率更高的 Dinic 算法或 ISAP 算法（参考《算法竞赛入门经典-训练指南》)。 对于竞赛来说, 实际更重要的在于网络流模型的建立, 这时把网络流算法作为模板来使用就可以了。