图论算法详解：预流推进与精确距离标号

"该资料主要涉及图论算法中的精确距离标号在预流推进算法中的应用，以及相关概念的解释。" 在图论算法中，精确的距离标号是求解网络流问题的一种关键工具，尤其在预流推进算法中扮演着重要角色。精确的距离标号通常用于描述在网络中从一个特定顶点（如源点Vs）到其他顶点的短路径长度。在描述的残留网络G'中，这个距离标号提供了从每个顶点到汇点Vt的有向路径长度的下界。具体来说： 1. 距离标号d(u)表示的是残留网络中从顶点u到汇点Vt的短有向路径长度的下限，这意味着实际路径的长度不会小于这个值。 2. 如果d(Vs)≥n，这意味着从源点Vs到汇点Vt在残留网络中不存在增广路径，因为没有路径的长度能超过源点的标号。 3. 允许路，即短增广路，是残留网络中使得流量可以增加的路径，它的长度不违反距离标号的约束。 为了计算精确的距离标号，可以对残留网络G'从汇点Vt开始进行反向广度优先搜索，这个过程的时间复杂度为O(m)，其中m是网络的边数。这样做可以将顶点按照它们到汇点的短路径长度进行层次划分，形成一个层次结构。 此外，预流推进算法是求解网络流问题的一种方法，它处理的是容量网络G中的预流。预流是满足每条弧流量不超过其容量限制且除了源点和汇点外所有顶点的赢余非负的网络流。赢余是流入顶点的流量减去流出流量的差值，而活跃顶点是指赢余大于零的非源点、非汇点顶点。当网络中存在活跃顶点时，表明预流还不是可行流。预流推进算法通过选择活跃顶点并将流量推进到邻近的顶点，尝试减少赢余至零，优先考虑将流量推向距离汇点更近的顶点，利用允许弧来推进流量。如果当前活跃顶点没有允许弧，就增加其距离标号以找到新的允许路径。 这本书《图论算法理论、实现及应用》由王桂平、王衍、任嘉辰编著，深入浅出地讲解了图论算法，包括图的基本概念、遍历、最短路径、网络流等问题，并通过ACM/ICPC竞赛题目来实践和应用这些算法。它适合作为高等院校计算机及相关专业图论课程的教材，也适合ACM/ICPC竞赛的准备和训练。图论，起源于欧拉解决的哥尼斯堡七桥问题，如今已成为描述和解决众多领域问题的强大工具。