cmu研究生算法之最大流

- 有向图。 源点，汇点。每条边都有一个容量。（假设这些都是整数。）目标：从源
点向汇点运送尽可能多的流量。

例：
s-->a, cap = 4. a-->c, cap = 3. c-->t, cap = 2.
s-->b, cap = 2. b-->d, cap = 3. d-->t, cap = 4.
c-->b, cap = 1. b-->c, cap = 2.

(* daizi注
2 3
s -------> b -------> d
4 | 2 | ^ | 4
v v |1 v
a -------> c -------> t
3 2
*)

正式的说,需要满足的规则是:
1. 容量限制: 任何边上的流量f(u,v) <= 容量c(u,v)
2. 刘亮守恒: 除了源点s和汇点t之外的任何顶点上,流入的流量 = 流出的流量

比如，上面例子中的最大流就是：5

怎么看出5就是最大的呢？注意到，这个流量填满了a->c和s->b这两条边。而且，如
果你把这两条边删除了，s到t就不可达了。换句话说，图上有一个容量是5的s-t割。
也就是说任何从s流到t的单位流量都必然在这些边上占用一个单位的容量。因此，
我们就证实了5确实最大的。

刚才我们所讨论的过程推广出来就是这样一个性质：最大流<=最小割。

定义：一个s-t割是这样一个边的集合，把这些边从网络中删除之后，s到t就不可达
了。或者，正式的说，一个割把顶点集合分成A,B两个集合，其中s在A中,t在B中，
而割中的边就是所有从A出发，到达B的所有边。

定义：割的容量就是割中所有边的容量的和。正式的说，就是所有从A到B的边的容
量的和。

容易看出，确实，s-t最大流 <= s-t最小割。

那怎么找到最大流并且证明它确实是最大的呢？一个十分自然的策略：找一条从s
到t的路，然后在这条路上执行尽可能多的流任务；然后看剩下的图，重复这个动
作，直到再也找不到从s到t的能够执行流任务的路了。这就是所谓的福特-福克森
算法。

Basic Ford-Fulkerson algorithm
------------------------------

只要存在一条从s到t的路径P有正的剩余容量，那么就在P上执行尽可能多的流任务。
（这就是所谓的增广路径）

定义：剩余容量 c_f(u,v) = c(u,v) - f(u,v)，为了方便我们令f(v,u) = -f(u,v)

--->例：在上面的例子中，最开始可以找到这样一条路经，s-->b-->c-->t。

注意：剩余容量可能比原来的容量还要大，这是因为我们可以在这条边的反方向上
运送一定的流量。比如：运送s->b->c->t之后，c->b的剩余容量就是3了。

为了明白起见，我们引入“剩余图”的概念。这个图是用来显示网络的剩余容量的：
它包含了所有拥有正的剩余容量的边，每条边都标记上了他的剩余容量。引入这个
概念的另一个好处是：如果我们拥有一个路径查找子程序，那么我们就可以直接把
它放在我们的FF算法的每一个迭代步骤中了。

-->注意：算法的运行时间是关于顶点个数和流量的多项式时间。因此，如果我们的
网络中出现大的容量，那么算法的执行时间就不一定是算法输入的多项式时间了。
下面，我们先证明算法的正确性，然后来修正以避免这个问题。

算法设计过程保证了算法找到是一个可行流，但为什么就是最大的呢？

证明：我们来看最后留下的剩余图。从算法的过程我们可以看出，在这个图中，s
到t是不可达的。假设A是包含s的那个连通片，而B是剩下的部分。令C=原始图(A,B)
割的容量--前面的讨论我们可以知道任何一个可行流的流量都不可能超过C。而下
面的论证我们就要说明我们确实找到了一个流量就是C的可行流。

我们来看算法每次迭代之后这个割的容量发生了什么样的变化。假设，在一次迭代
中我们寻找到了一个路径，并且在这个路径上运送了k个单位的流量。那么，即使
这条路径在A,B之间绕来绕去的，路径每次从A到B时我们就为从A到B的流增加了k个
单位，而每次从B到A时我们就从A到B的流中减少了k个单位。而从A到B的次数比从
B到A的次数要多一次，因此，这个割剩余容量将会减少k，也就是说这个割的剩余
容量的减少恰好就是网络中流量的增加。因此，到最后，当其剩余容量减少到0的
时候，整个网络的流量就增加到了最大值C。

实际上，我们这里就证明了所谓的最大流-最小割定理。

任何图中，从s到t的最大流等于所有(s,t)割的容量的最小值。

前面，最开始我们说最大流<=最小割。现在我们看到我们的算法确实找到了一个可
行流，他的值和某个割的容量相等，也就是说不可能比最小割更小。

同样，我们也证明了整数流定理：如果所有的容量都是整数，那么网络将会有一个
最大流，并且在这个最大流中所有的流量都是整数。

Bipartite Maximum matching problem
----------------------------------

网络流的一个很漂亮的应用就是解决二分图的匹配问题。比如，为新生安排宿舍。

一个匹配是一些边的集合，这些边中没有任意两条边具有公共顶点。这儿我们需要
求得是完美匹配--完美匹配中是这样一个匹配，他把二分图中左边的每个顶点都
通过一条边连接到右边的某个顶点上去。更一般的是我们需要求一个最大匹配--就
是拥有最多边数的匹配。

Algorithm to solve:
------------------

1。建立一个源点s，把它和图中所有左边的顶点都连接起来。然后把右边的顶点都
和一个新的会点t连接起来。并且把图中所有的边都定向成为从左到右，把图中所
有的边都赋予一个上限为1的容量。
2。寻找一个从s到t的最大流
3。对应这个最大流输出匹配。

EDMONDS-KARP #1
---------------

FF算法的一个问题是如果图中容量很大的话，他的运行时间将可能会很长，因为算法
迭代次数是O(F)，其中F时最大流的值，而这个值不一定是问题输入规模的多项式级
别大小。

E-K给出了两个很自然的策略解决了这个问题。

1：每次总是选择瓶颈最大的可增广路。

结论：这个改进将使得FF算法进行O(m lg F)次迭代。

首先：我们怎么才能够找到一个图中的拥有最大瓶颈的路径呢？
答案：使用一个类似Prim的贪心算法。开始的时候，令U = {s}，总是把离开集合U的
拥有最大容量的边给放进来。这样行吗？任何一个时刻，假设我们得到的集合是U，
而离开U的拥有最大容量的边的容量是c。那么，任何从s到顶点集合V-U的路径的瓶颈
至少是c。因此，把这条边放进来是安全的。

结论的证明：如果当前的剩余图拥有一个最大流f，那么我们将证明图中的最大瓶颈
路径的容量至少是f/m。为什么呢？让我们来执行上面的算法：如果我们在某个时刻
发现所有离开U的边的容量都小于f/m，那么这就意味着发现了一个割，他的容量小
于f，这样就产生了一个矛盾。

因此，每次迭代之后，剩余图中的最大流的流量至少减少了1/m，因此通过m次迭代
之后，流量下降了1/e，而m * lg F次迭代之后，流量将会<1。

回顾：最大流的FF算法，最大流最下割定理，整数流定理，EK第一算法。

EK方法：
首先，我们通过建立一颗树来寻找我们需要的路径。最开始令集合U={s},然后每次
从离开这个集合的所有边中找到最宽的也就是具有最大容量上限的边加进来。这将
得到一棵树，树中从s到t的路径就是我们需要的。我们论证得到，找到的路径的容
量至少是图的最大流的1/m。证明很简单，如果任意时刻我们发现所有离开U的边的
容量都小于f/m，那么这个时候所有离开U的边的容量的总和 小于等于割的容量矛盾。因此，我们每次寻找到的这条路径将会使得整个图的最大
流的流量减少至少1/m。

一个有趣的应用：3-D图象处理。（略）

EDMONDS-KARP #2
---------------

EK2: 总是选择最短路径。

结论：通过这个策略，算法将至多执行O(mn)次迭代。因此，如果我们每次使用BFS
来寻找最短路，那么算法的执行时间是O(nm^2)。

这里我们给出两个证明，他们的前部分是一样的。

证明1：令d(v)是当前剩余图中s到v的最短路的长度。为了方便起见，我们把图
按照顶点离s的距离进行分层。现在我们来考虑每次迭代，每次迭代都可能往图中
添加新的边，但是d(v)却永远不会减少。为什么呢？因为所有添加的边在这个层次
图中都是从d值较高到d值较低的。

每次我们找到一个这样的路径，我们至少使得路径上的一条边达到饱和。假设我们
使得边u->v饱和了，这里u在第i层，v在第i+1层。如果我们再次把u->v添加进来的
话，那么u至少在i+2层或者更下面。为什么？因为当我们再次把这条边添加进来的
时候，必然有一条最短路径经过v->u。而一个顶点的级别永远不会减小，因此v至
少在级别i+1，所以u至少在级别i+2。

因此，任何给定的边被删除的次数至多是n/2。而每次迭代将会删除或者重新添加
至少一条原来图中的边，因此至多有mn次迭代。

证明2：另外一个办法是观察s到t的距离。最开始通过BFS我们的到了一个层次图，
我们一直使用这个层次图直到d(t)发生了变化为止。如果d(t)没有发生改变，我们
每次找到的最短路必然是前向的，也就是从d值小的到d值大的，因此每次迭代至少
删除一条前向边，而直到d(t)改变我们至多删除m次，又因为d(t)至多增加n次。因
此我们至多进行mn次迭代。

DINIC & MPM
===========

我们能够做的更快一些么？？

前面的算法需要O(mn)次迭代，而每次需要O(m)的时间，因此总共需要O(m^2 n)。
下面我们试着降到O(n^3)。

想法：假设d=d(t)，我们将试着一次性的找到很多到t的长度为d的路径。为了做到
这个，我们看前面得到的层次图（我们不考虑所有的后向边以及两个端点在同一层
的边）。我们现在尝试着在这个图中执行尽量多的流量，然后我们才重新计算剩余
图。

术语：一个充满了这个剩余图的流称之为块流。

因此我们的目标就是在这个剩余图中在O(n^2)的时间内找到一个块流。

我们定义c(v)=顶点v的容量：也就c_in[v],c_out[v]的最小值，这里c_in[v]是所有
v的入边的容量的和，而c_out[v]类似。

算法：

-找到具有最小容量c的顶点v。如果他的容量是0，oh yeah--我们就可以把他和与
他相关联的边都删除掉，并且更新他的邻居的容量值。

-如果c不为0，那么我们将从s运送c个单位流到v，然后从v运送到t。你可能觉得这
不又回到原来的问题了么？但是，这里有点值得注意：因为v具有最小的容量，
我们可以使用任何的贪心策略来从其他顶点流入流出c的流量而不会被堵住。这一
点意味着，我们可以在O(m)的时间内充满v。

（* daizi
nnd，想了好久才明白具体怎么做的
首先，为了从s运送c到v，我们从v开始向上考虑，把任意一条从v向上的边给充满，
如果不能够充满，说明还没有安置的流量就这些了，全部扔在这条边上就是了，
为什么一定能够找到这样一条边呢，：）

然后假设我们刚才填充的这条边是u->v，那么我们就有一些流量需要在u继续往上
进行处理，使用刚才在v点同样的办法，直到一直处理到了s，一路上肯定是不会
出现什么障碍的。

然后我们将c从v运送到t，我们在构造这个层次图的时候很容易就可以保证所有从
s出发的路径都会在t终结，这样就好办了，使用上面同样的办法，只是处理的方
向是从v到t了。

这样，我们刚才处理的过程就容易得到下面的下面所谓的性质了。
*）

上面的算法给了我们一个可以在O(mn)的时间内充满这个层次图的算法，下面进一步
分析。

为了得到我们需要的界，我们需要这样一个性质：当我们在上面的对每个新的顶点v
执行算法的步骤中，保证对每条边我们只检查一次，对其做完所有需要的操作
之后才会去做下一条边。这点意味着，我们可以把运行时间分成两个部分来考虑：
a）花在被充满的边上的时间 b）花在没有被充满的边上的时间。对于a），因为我们
每次充满一条边就会把它从图中删除，所以a）的总时间是O(m)。

因此我们的时间主要由b）来决定，而b）对应的边在对每个新的顶点v的执行过程中
至多出现O(n)次，因此总的时间是O(n^2)。而我们可以在O(m)的时间内重新计算新
的层次图，所以我们就可以在O(n m + n n^2)时间完成整个算法，也就是O(n^3)。