学一个新算法，总要翻多而杂的blog，收获不多。所以我就致力于把学习笔记总结，希望一遍看懂。 简单入门 （但是不全）

网络流用于解决流量问题

网络流:所有弧上流量的集合f={f(u,v)},称为该容量网络的一个网络流.

定义：带权的有向图G=(V,E)，满足以下条件，则称为网络流图(flow network)：

弧的流量:通过容量网络G中每条弧< u,v>,上的实际流量(简称流量),记为f(u,v);

对于任意一个时刻，设f(u,v)实际流量，则整个图G的流网络满足3个性质：

可行流:在容量网络G中满足以下条件的网络流f,称为可行流.

在一个网络流图上，找到一条源到汇的路径（即找到了一个流量）后，对路径上所有的边，其容量都减去此次找到的量，对路径上所有的边，都添加一条反向边，其容量也等于此次找到的流量，这样得到的新图，就称为原图的“残余网络”

下面介绍网络流理论中一个最为重要的定理 最大流最小割定理(Maximum Flow, Minimum Cut Theorem): 网络的最大流等于最小割

具体的证明分三部分 1.任意一个流都小于等于任意一个割 这个很好理解 自来水公司随便给你家通点水 构成一个流 恐怖分子随便砍几刀 砍出一个割 由于容量限制 每一根的被砍的水管子流出的水流量都小于管子的容量 每一根被砍的水管的水本来都要到你家的 现在流到外面 加起来得到的流量还是等于原来的流 管子的容量加起来就是割 所以流小于等于割 由于上面的流和割都是任意构造的 所以任意一个流小于任意一个割 2.构造出一个流等于一个割 当达到最大流时 根据增广路定理 残留网络中s到t已经没有通路了 否则还能继续增广 我们把s能到的的点集设为S 不能到的点集为T 构造出一个割集C[S,T] S到T的边必然满流 否则就能继续增广 这些满流边的流量和就是当前的流即最大流 把这些满流边作为割 就构造出了一个和最大流相等的割 3.最大流等于最小割 设相等的流和割分别为Fm和Cm 则因为任意一个流小于等于任意一个割 任意F≤Fm=Cm≤任意C 定理说明完成，证明如下： 对于一个网络流图G=(V,E)，其中有源点s和汇点t，那么下面三个条件是等价的： 1. 流f是图G的最大流 2. 残留网络Gf不存在增广路 3. 对于G的某一个割(S,T)，此时f = C(S,T) 首先证明1 => 2：

我们利用反证法，假设流f是图G的最大流，但是残留网络中还存在有增广路p，其流量为fp。则我们有流f’=f+fp>f。这与f是最大流产生矛盾。 接着证明2 => 3：

假设残留网络Gf不存在增广路，所以在残留网络Gf中不存在路径从s到达t。我们定义S集合为：当前残留网络中s能够到达的点。同时定义T=V-S。 此时(S,T)构成一个割(S,T)。且对于任意的u∈S,v∈T，有f(u,v)=c(u,v)。若f(u,v) < c(u,v)，则有Gf(u,v) > 0，s可以到达v，与v属于T矛盾。 因此有f(S,T)=Σf(u,v)=Σc(u,v)=C(S,T)。 最后证明3 => 1：

由于f的上界为最小割，当f到达割的容量时，显然就已经到达最大值，因此f为最大流。 这样就说明了为什么找不到增广路时，所求得的一定是最大流。

这篇文章对理解概念也是不错的。

好了概念就讲到这里，下面看一看具体的算法

下面是所有最大流算法的精华部分：引入反向边 为什么要有反向边呢？ 我们第一次找到了1-2-3-4这条增广路，这条路上的delta值显然是1。于是我们修改后得到了下面这个流。（图中的数字是容量） 这时候(1,2)和(3,4)边上的流量都等于容量了，我们再也找不到其他的增广路了，当前的流量是1。

但这个答案明显不是最大流，因为我们可以同时走1-2-4和1-3-4，这样可以得到流量为2的流。

那么我们刚刚的算法问题在哪里呢？问题就在于我们没有给程序一个”后悔”的机会，应该有一个不走(2-3-4)而改走(2-4)的机制。那么如何解决这个问题呢？回溯搜索吗？那么我们的效率就上升到指数级了。

而这个算法神奇的利用了一个叫做反向边的概念来解决这个问题。即每条边(I,j)都有一条反向边(j,i)，反向边也同样有它的容量。

我们直接来看它是如何解决的：

在第一次找到增广路之后，在把路上每一段的容量减少delta的同时，也把每一段上的反方向的容量增加delta。即在Dec(c[x,y],delta)的同时，inc(c[y,x],delta)

我们来看刚才的例子，在找到1-2-3-4这条增广路之后，把容量修改成如下

这时再找增广路的时候，就会找到1-3-2-4这条可增广量，即delta值为1的可增广路。将这条路增广之后，得到了最大流2。

那么，这么做为什么会是对的呢？我来通俗的解释一下吧。

事实上，当我们第二次的增广路走3-2这条反向边的时候，就相当于把2-3这条正向边已经是用了的流量给”退”了回去，不走2-3这条路，而改走从2点出发的其他的路也就是2-4。（有人问如果这里没有2-4怎么办，这时假如没有2-4这条路的话，最终这条增广路也不会存在，因为他根本不能走到汇点）同时本来在3-4上的流量由1-3-4这条路来”接管”。而最终2-3这条路正向流量1，反向流量1，等于没有流量。

求最大流的过程，就是不断找到一条源到汇的路径，若有，找出增广路径上每一段[容量-流量]的最小值delta，然后构建残余网络，再在残余网络上寻找新的路径，使总流量增加。然后形成新的残余网络，再寻找新路径…..直到某个残余网络上找不到从源到汇的路径为止，最大流就算出来了。

先从Ford-Fulkerson算法看起？

现在假设每条边的容量都是整数。这个算法每次都能将流至少增加1。由于整个网络的流量最多不超过图中所有的边的容 量和C，从而算法会结束 。 这个算法实现很简单但是注意到在图中C可能很大很大 比如说下面这张图

如果运气不好这种图会让你的程序执行200次dfs，虽然实际上最少只要2次我们就能得到最大流 如何避免上述的情况发生？

在每次增广的时候，选择从源到汇的具有最少边数的增广路径,也就是说！不是通过dfs寻找增广路径，而是通过bfs寻找增广路径。 这就是Edmonds-Karp 最短增广路算法 已经证明这种算法的复杂度上限为nm2 (n是点数，m是边数）

板子题 ：codevs1933 poj1273