文件名称：预流推进算法的最大流模板
文件大小：3KB
文件格式：CPP
更新时间：2012-09-02 11:48:16
最大流模板 预流推进算法 距离标号
预流推进算法是不同与增广路思想的另一种求最大流的算法，主要思想是把流从源点经过边，并通过调整顶点的标号来把流压入汇点。 该算法需要维护一个装有活跃顶点的标号，所谓活跃定点则是流出量小于流入量的顶点，则具有超额量，欲使该顶点平衡（流出==流入），则需要把该定点积累的流压出，被压入流的顶点只能是距离标号比该点标号小1且这条边未满流的顶点，若不存在这样的顶点但是改点仍未活跃顶点，则需要把该点的距离标号加1. 这只是利用普通的FIFO队列，为了加速算法，可以维护一个优先队列，以顶点的距离标号为优先级，距离标号大的先出列。