有关网络流中的反向弧和增广路

增广路

以最大流为例子，考虑求最大流。

首先，假如所有边上的流量都没有超过容量(不大于容量)，那么就把这一组流量，或者说，这个流，称为一个可行流。一个最简单的例子就是，零流，即所有的流量都是0的流。

我们就从这个零流开始考虑，假如有这么一条路，这条路从源点开始一直一段一段的连到了汇点，并且，这条路上的每一段都满足流量<容量，注意，是严格的<,而不是<=。那么，我们一定能找到这条路上的每一段的(容量-流量)的值当中的最小值minCap。我们把这条路上每一段的流量都加上这个minCap，一定可以保证这个流依然是可行流，这是显然的。

这样我们就找到了一个更大的流，他的流量是之前的流量加上minCap，这个就是增广路。

不断地从起点开始寻找增广路，每次都对其进行增广。直到源点汇点不连通，也就是找不到增广路。这个时候当前的流量就是最大流。

反向弧

一开始对反向弧是什么，以及有什么作用完全不是很懂。

看了comzyh的博客少许理解。现在来解释下。

对于最大流。每次进行建图的时候，总是需要建立一条正向边以及一条反向边。对于每次的增广，你需要做的是在图上的残量网络上首先修改的cap值把cap[u,v]减去minCap（这是正向的），然后对于的cap把cap[v,u]加上minCap（这是逆向的）。这样就表示正向边的容量减小了，反向边的容量增加了。这样做有什么好处呢？

举一个例子。

一个图,(请自行画图),描述(u -> v, 流量)，6个顶点，1为源点，6为汇点。  
1 -> 2  2  
1 -> 3  2  
2 -> 4  2  
3 -> 4  2  
2 -> 5  2  
5 -> 6  2  
4 -> 6  2

首先不考虑反向弧。

现在我们不断地从s点开始寻找增广路，每次都进行增广。假设我们每次更新残余网络只更新正向弧流量，不更新反向弧的流量。

我们找到了一条增广路：1 -> 2 -> 4 -> 6，minCap是2，增广路流量为2。

现在开始找第二条增广路：1 -> 3 -> 4找不下去了。发现这个残余网路已经不能使得s-t连通了，所以说2就是最大流。

可是实际上的最大流为4，并不是2。

仔细想想为什么会出现这样的问题。因为我们没能给程序反悔的机会，也就是说，我们增广路的时候也许并不是最终的流的形式，我们也许需要修改的。

于是就出现了反向边的概念。每条边都有它的反向边，并且反向边也有它的容量。

就是说每次增广路的时候，更新残余网络不仅减少正向弧容量，还增加反向弧的容量。

怎么说呢，对于刚刚的例子：1 -> 2 -> 4 -> 6找到这条增广路的时候，把相应的每条正向边容量减小。反向边容量增加。然后可以再绘制一下新的残余网络了。（有助于理解）

现在对于这个图，你第二次增广的时候1 -> 3 -> 4，然后你发现4 -> 2 还有一条容量为2的弧可以跑。这个时候就可以继续流最终实现的增广路就能成为1 -> 3 -> 4 -> 2 -> 5 -> 6并且流量为2。

这个时候最大流就为4，可以再画一遍新的残余网络。

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

因为我们是朋友，所以你可以使用我的文字，但请注明出处：http://alwa.info