算法: 最大流与最小割

2019-03-06 本文已影响48人写代码的海怪

什么是最大流

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

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

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

那最小割是啥？就是一堆边的集合，这些边权重加起来应该是要等于最大流的值，且这些边都是从 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，不用去管前面那个是什么意思。

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