Skip to content

Tag Archives: Relabel-to-Front

求最大流的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