Skip to content

Tag Archives: 最大流

求最大流的Relabel-to-Front算法

除了用各种方法在剩余网络中不断找增广路(augmenting)的Ford-Fulkerson系的算法外,还有一种求最大流的算法被称为压入与重标记(Push-Relabel)算法。它的基本操作有:压入,作用于一条边,将边的始点的预流尽可能多的压向终点;重标记,作用于一个点,将它的高度(也就是label)设为所有邻接点的高度的最小值加一。Push-Relabel系的算法普遍要比Ford-Fulkerson系的算法快,但是缺点是相对难以理解。 Relabel-to-Front使用一个链表保存溢出顶点,用Discharge操作不断使溢出顶点不再溢出。Discharge的操作过程是:若找不到可被压入的临边,则重标记,否则对临边压入,直至点不再溢出。算法的主过程是:首先将源点出发的所有边充满,然后将除源和汇外的所有顶点保存在一个链表里,从链表头开始进行Discharge,如果完成后顶点的高度有所增加,则将这个顶点置于链表的头部,对下一个顶点开始Discharge。 Relabel-to-Front算法的时间复杂度是O(V^3),还有一个叫Highest Label Preflow Push的算法复杂度据说是O(V^2*E^0.5)。我研究了一下HLPP,感觉它和Relabel-to-Front本质上没有区别,因为Relabel-to-Front每次前移的都是高度最高的顶点,所以也相当于每次选择最高的标号进行更新。还有一个感觉也会很好实现的算法是使用队列维护溢出顶点,每次对pop出来的顶点discharge,出现了新的溢出顶点时入队。 Push-Relabel类的算法有一个名为gap heuristic的优化,就是当存在一个整数0<k<V,没有任何顶点满足h[v]=k时,对所有h[v]>k的顶点v做更新,若它小于V+1就置为V+1。不过这个我还没实现,因为现在算法的效率我已经很满意了,以后有空再实现吧。 今天实现的Relabel-to-Front比昨天的距离标号最短增广路又要高效一倍左右。最后感叹一下,网络流真是有趣啊……甚至都想买那本专门讲网络流的书来看看。 示例程序(还是USACO Training Ditch,不过都是自己出数据测的): ditch(preflow).cpp

求最大流的使用距离标号的最短增广路算法

求最大流有一种经典的算法,就是每次找增广路时用BFS找,保证找到的增广路是弧数最少的,也就是所谓的Edmonds-Karp算法。可以证明的是在使用最短路增广时增广过程不超过V*E次,每次BFS的时间都是O(E),所以Edmonds-Karp的时间复杂度就是O(V*E^2)。 如果能让每次寻找增广路时的时间复杂度降下来,那么就能提高算法效率了,使用距离标号的最短增广路算法就是这样的。所谓距离标号,就是某个点到汇点的最少的弧的数量(另外一种距离标号是从源点到该点的最少的弧的数量,本质上没什么区别)。设点i的标号为D[i],那么如果将满足D[i]=D[j]+1的弧(i,j)叫做允许弧,且增广时只走允许弧,那么就可以达到“怎么走都是最短路”的效果。每个点的初始标号可以在一开始用一次从汇点沿所有反向边的BFS求出,问题就是如何在增广过程中维护这个距离标号。 维护距离标号的方法是这样的:当找增广路过程中发现某点出发没有允许弧时,将这个点的距离标号设为由它出发的所有弧的终点的距离标号的最小值加一。这种维护距离标号的方法的正确性我就不证了。 由于距离标号的存在,由于“怎么走都是最短路”,所以就可以采用DFS找增广路,用一个栈保存当前路径的弧即可。当某个点的距离标号被改变时,栈中指向它的那条弧肯定已经不是允许弧了,所以就让它出栈,并继续用栈顶的弧的端点增广。为了使每次找增广路的时间变成均摊O(V),还有一个重要的优化是对于每个点保存“当前弧”:初始时当前弧是邻接表的第一条弧;在邻接表中查找时从当前弧开始查找,找到了一条允许弧,就把这条弧设为当前弧;改变距离标号时,把当前弧重新设为邻接表的第一条弧,还有一种在常数上有所优化的写法是改变距离标号时把当前弧设为那条提供了最小标号的弧。当前弧的写法之所以正确就在于任何时候我们都能保证在邻接表中当前弧的前面肯定不存在允许弧。 还有一个常数优化是在每次找到路径并增广完毕之后不要将路径中所有的顶点退栈,而是只将瓶颈边以及之后的边退栈,这是借鉴了Dinic算法的思想。注意任何时候待增广的“当前点”都应该是栈顶的点的终点。这的确只是一个常数优化,由于当前边结构的存在,我们肯定可以在O(n)的时间内复原路径中瓶颈边之前的所有边。 我程序做了很多优化(甚至包括动态内存分配的时候使用placement new进行优化),最终能做到比wxs写的dinic快了大约一倍,但程序只有一百二十多行,我对这个结果很满意。距离标号增广的确是一个非常优秀非常实用的算法。 示例程序(USACO Training Ditch): ditch.cpp