Ford-Fulkerson方法中的容量缩放（Capacity Scaling）优化

题目描述
在最大流问题中，给定一个有向图，其中每条边有一个非负容量，以及源点s和汇点t，目标是找到从s到t的最大流量。Ford-Fulkerson方法通过不断在残留图中寻找增广路径来增加流量，但若增广路径选择不当（如使用DFS可能陷入多次小流量增广）。容量缩放优化通过优先处理高容量边来提升效率：设定一个缩放参数Δ，初始为最大边容量的最小2的幂次，每轮只考虑容量≥Δ的边构建子图进行增广，当无增广路时将Δ减半，直到Δ=0。这确保算法在O(m² log C)时间内完成（m为边数，C为最大容量），优于基础Ford-Fulkerson的O(mC)。

解题步骤

1. 初始化

   • 计算图中所有边的最大容量C，取Δ为不小于C的最大2的幂次（如C=13则Δ=8）。
   • 初始化流量f为0，残留图G_f与原图相同。

2. 缩放阶段循环（当Δ ≥ 1时）

   • 构建缩放子图：在残留图G_f中，仅保留剩余容量≥Δ的边。
   • 在缩放子图中寻找增广路径：使用BFS或DFS从源点s出发，检查是否能到达汇点t。
     • 若存在增广路径p，则沿p增加流量，增量为路径上最小剩余容量（必≥Δ）。更新G_f的边容量（正向边减流量，反向边加流量）。
     • 重复搜索直到当前缩放子图中无s-t路径。
   • Δ = Δ / 2（向下取整，进入下一缩放阶段）。

3. 终止与输出

   • 当Δ=0时，算法结束，当前流量f即为最大流。

循序渐进讲解

• 为何需要缩放？
  基础Ford-Fulkerson可能因增广路径容量过小导致效率低（如边容量差大时）。缩放通过Δ优先处理“大容量”边，避免早期浪费在细小增广上，类似贪心策略。

• 缩放阶段示例
  假设图有边容量[1, 17]，最大容量C=17，Δ初始为16。

  • Δ=16：仅容量≥16的边被考虑，若存在增广路径则增广（如直接增广s→t边）。
  • Δ=8：子图包含容量≥8的边，继续增广。每阶段可能多次增广直至无路径。
  • 最终Δ=1时处理所有边，确保不漏解。

• 复杂度优势
  每缩放阶段最多增广m次（因每阶段至少一条边饱和），共log C阶段，BFS寻路为O(m)，总复杂度O(m² log C)。相比基础O(mC)，当C很大时更高效。

关键点

• 缩放参数Δ指数下降，保证阶段数可控。
• 每阶段子图忽略低容量边，加速增广路径搜索。
• 最终Δ=0时覆盖所有边，确保正确性。