预流推进算法详解：最大网络流的求解

"一般的预流推进算法是一种网络流算法，用于寻找有向图中的最大流。该算法通过迭代过程更新网络中的流量，直至找到最大流。每次迭代包括推进运算和高度重新标号运算。饱和推进是指推进的流量达到边的残留容量，而非饱和推进则指推进的流量未达到边的残留容量。当网络中不再有活顶点，即所有顶点的存流都为零，除了源点s和汇点t，此时的预流即为最大流。算法开始时，构建初始预流，使源点s的每条出边流量等于其容量，其他边流量为零，并构造有效高度函数。在迭代过程中，若残量网络中没有活顶点，则算法结束；否则选择活顶点并尝试沿可推流边推流，或者更新高度函数后继续迭代。网络流涉及的术语包括：源点s、汇点t、边的容量、流量、可行流、饱和边等。可行流需满足容量约束和平衡约束，即流量不超过边的容量且所有中间顶点的流入流出流量相等，源点的净输出量等于汇点的净输入量。" 在网络流算法中，预流推进算法是一种经典方法，其主要目标是在一个有向图中找出从源点s到汇点t的最大流量。这个过程可以被看作是在满足容量约束和平衡约束的情况下，尽可能多地从s向t传输“流”。有向图中的每个顶点代表一个节点，每条边带有容量限制，这限制了通过这条边的流的大小。网络流问题有多种应用，包括运输问题、电路设计、数据包路由等。 预流推进算法首先建立一个初始预流，即从源点s向所有相邻节点分配等于边容量的流量，其他边的流量设为零。然后，算法通过迭代来逐步增加这个预流，直到找不到能增加总流量的路径，即不存在增广路。增广路是网络中一条可以从s到t且沿途每条边都未饱和的路径，增加预流沿着增广路的方向进行。 在每次迭代中，算法会选择一个活顶点，即一个仍有未用完的容量的节点，尝试沿它的出边推流。如果所有的出边都已经饱和，算法会进行高度重新标号，调整节点的高度以寻找新的增广路。高度函数是一个关键工具，用于确保不存在增广路，从而保证算法最终找到最大流。当网络中没有活顶点时，算法结束，此时的预流是网络中的最大流，且满足所有边的流量不超过其容量，源点和汇点的净流量之和即为最大流的值。 总结起来，一般的预流推进算法是通过迭代和高度调整策略来寻找有向图中的最大流，它依赖于增广路的概念和容量约束、平衡约束的性质。算法的效率和正确性已经得到了理论证明，使其成为解决网络流问题的常用工具。