最大流问题（Capacity Scaling 优化）

题目描述：给定一个有向图G=(V,E)，其中每条边(u,v)∈E有一个非负容量c(u,v)≥0。指定源点s和汇点t。Capacity Scaling优化是一种改进的Ford-Fulkerson方法，通过逐步处理容量值较大的边来减少增广路径的寻找次数。

解题过程：

1. 基本思想
   Capacity Scaling的核心思想是"按位处理"。我们不是一次性地寻找所有可能的增广路径，而是分阶段进行。在每个阶段，我们只考虑容量不小于某个阈值Δ的边，这样可以在早期阶段快速推送大量流量，后期阶段处理细微调整。

2. 算法准备

   • 初始化流量f为0
   • 计算最大容量C = max{c(u,v) | (u,v)∈E}
   • 初始化缩放因子Δ = 2^⌊log₂C⌋（小于等于C的最大2的幂）

3. 缩放阶段循环
   while Δ ≥ 1:
   a. 在残量图G_f中，只保留那些残量容量r_f(u,v) ≥ Δ的边
   b. 在缩放后的残量图中寻找s-t增广路径
   c. 如果找到增广路径，沿路径推送尽可能多的流量（至少Δ单位）
   d. 如果找不到更多增广路径，令Δ = Δ/2

4. 详细执行步骤
   步骤1：初始化阶段

   • 设置f(u,v)=0对所有边(u,v)
   • 计算C = max{c(u,v)}
   • 设置Δ = 2^⌊log₂C⌋

   步骤2：缩放循环
   while Δ > 0:

   • 构建缩放残量图：只包含r_f(u,v) ≥ Δ的边
   • 在缩放残量图中用DFS/BFS寻找s-t路径
   • while 存在增广路径p:
     • 计算路径p的瓶颈容量bottleneck = min{r_f(u,v) | (u,v)∈p}
     • 沿路径p推送bottleneck单位流量
     • 更新残量容量：前向边减流量，后向边加流量
   • Δ = Δ / 2

5. 算法正确性分析

   • 每个缩放阶段结束时，当前流量在缩放残量图中是最大流
   • 当Δ=1时，算法退化为标准Ford-Fulkerson
   • 由于我们按2的幂次缩放，保证了最终能找到真正最大流

6. 复杂度分析

   • 缩放阶段数：O(log₂C)
   • 每个阶段最多找O(m)条增广路径
   • 总复杂度：O(m² log₂C)，优于基本Ford-Fulkerson的O(mC)

7. 实例演示
   考虑一个简单网络：s→A→t，s→B→t，边容量分别为5和3。

   • 初始Δ=4（因为最大容量5，2²=4≤5）
   • Δ=4阶段：只能走s-A-t（容量5≥4），推送4单位流量
   • Δ=2阶段：所有边都可用，继续推送剩余流量
   • Δ=1阶段：精细调整，达到最大流8

这种优化特别适合边容量差异大的情况，能显著减少增广路径的寻找次数。