Ford-Fulkerson 方法中的容量缩放（Capacity Scaling）优化 题目描述 给定一个有向图，其中每条边有一个非负整数容量，以及一个源点 \( s \) 和一个汇点 \( t \)，求从 \( s \) 到 \( t \) 的最大流。Ford-Fulkerson 方法通过不断寻找增广路径来增加流量，但基础版本可能因路径选择不当而效率低下（尤其当容量为无理数时可能不终止）。容量缩放（Capacity Scaling）是一种优化策略，通过优先处理容量较大的边，确保算法在多项式时间内运行（对于整数容量）。 核心思想 容量缩放引入一个参数 \( \Delta \)，初始时设为大于最大容量的最小 2 的幂（即 \( \Delta = 2^{\lfloor \log_ 2 U \rfloor} \)，其中 \( U \) 是最大边容量）。在每轮迭代中，仅考虑容量不小于 \( \Delta \) 的边构成的子图（称为 \( \Delta \)-残量图），寻找增广路径。当无法找到更多增广路径时，将 \( \Delta \) 减半，重复过程直到 \( \Delta = 0 \)。这保证了每轮增广的流量至少为 \( \Delta \)，从而限制迭代次数。 解题步骤 初始化 ： 设流量 \( f = 0 \)。 计算最大容量 \( U = \max\{c(e) \mid e \in E\} \)。 设 \( \Delta = 2^{\lfloor \log_ 2 U \rfloor} \)（例如，若 \( U = 17 \)，则 \( \Delta = 16 \)）。 容量缩放循环 （当 \( \Delta \geq 1 \) 时）： 构建 \( \Delta \)-残量图 \( G_ f(\Delta) \) ： 保留残量容量 \( c_ f(e) = c(e) - f(e) + f(e^{\text{reverse}}) \geq \Delta \) 的边（注意：反向边也可能满足条件）。 在 \( G_ f(\Delta) \) 中寻找增广路径 ： 使用 DFS 或 BFS 在 \( \Delta \)-残量图中找一条从 \( s \) 到 \( t \) 的路径。若存在路径 \( p \)，则： 计算路径的瓶颈容量 \( b = \min\{c_ f(e) \mid e \in p\} \)（由于筛选条件，必有 \( b \geq \Delta \)）。 沿路径增加流量 \( b \)，更新残量图。 重复寻找路径直到不存在增广路径。 缩放参数减半 ：设 \( \Delta = \Delta / 2 \)。 终止 ：当 \( \Delta = 0 \) 时，算法结束，当前流量 \( f \) 即为最大流。 为什么有效？ 每轮缩放阶段（固定 \( \Delta \)）的增广次数至多为 \( 2m \)（其中 \( m \) 是边数），因为每次增广至少饱和一条边（使其残量容量降至 \( < \Delta \)）。 缩放阶段数为 \( O(\log U) \)，总增广次数为 \( O(m \log U) \)，每次增广需 \( O(m) \) 时间，总复杂度为 \( O(m^2 \log U)\)。 优先处理大容量边，避免小流量增广造成的低效。 实例说明 考虑一个简单图：边 \( (s, a): 5, (a, t): 3, (s, b): 3, (b, t): 5 \)，最大流为 6（两条路径：s→a→t 流 3，s→b→t 流 3）。 初始 \( \Delta = 4 \)（因 \( U = 5 \)，取 \( 2^2 = 4 \)）。 \( \Delta = 4 \) 时，残量图中只有边容量 ≥4 的边（如 (s,a):5, (b,t):5），可找到路径 s→a→t（瓶颈 3？但注意 (a,t) 容量 3 < 4，不满足条件！实际上此时无增广路径），直接进入 \( \Delta = 2 \)。 \( \Delta = 2 \) 时，所有边均被保留，通过两次增广得到最大流 6。 此优化确保算法在整数容量下高效收敛。