最大流最小割经典例题_算法:最大流与最小割

什么是最大流

最大流要解决的问题是从 S 到 T 怎么才能最大地将数据运到另一边。这个“数据”可以是水，或者网络数据包。举个例子

在上面这个图中将数据从 S 运到 T，其中边的权值称为 Capacity 即，在这条边中流动的数据不能超过 Capacity 值，

。

这个图很简单，我们很容易就看出来最大流是 5。流动方向为

S - 1 - T: 2

S - 1 - 2 - T: 1

S - 2 - T: 2

那最小割是啥？就是一堆边的集合，这些边权重加起来应该是要等于最大流的值，且这些边都是从 S 那边到 T 这边的。

简单思路

我们先来大概想个方法去找最大流。其实找最大流的简单方法就是一条路一条路试呗，刚好试到上面三条路就发现是最大的了。

但是总有不如意的时候，比如我们先走 S - 1 - 2 - T，用了流 3，那么整个网络可以再尝试的路只剩下这些了：

现在我们就陷入僵局了，没路可以尝试了，最大流就变成了 3，明显错了。正确的做法应该是这次没找到好的可以进行“反悔”操作，回退上一步之类的，然后再去尝试找最大流嘛。这就需要用到残余网络了。

残余网络

残余网络也叫做 Residual Network，它的出现可以使得我们每次找路的时候进行 “反悔” 操作。比如上面走了 S - 1 - 2 - T 后，残余网络是这样的

可以看到正向走了多少，那么就画一条反向边，这条边的权值就等于前面走了多少流。因为现在有边 2 -> 1 了，所以可以找到一条路 S - 2 - 1 - T，用了流 2，再加上前面找的 3，所以最大流是 5。

这就做完了，其中最小割就是集合 {S - 1, S - 2}: 5。这里所找的路叫做 Augmenting path，反正就是 path，不用去管前面那个是什么意思。

Ford-Fulkerson 算法

画图好画，那程序上怎么实现呢？其实程序上我觉得更容易。伪代码如下

首先初始化 Residual Network G

使用 DFS 或者 BFS 去找 Augmenting Path，找到一个就加入到 Residual Network G

因为使用了之后边是反过来的，所以总会出现 S 走不到 T 的时候，那个时候就停止算法即可