最大流问题（Ford-Fulkerson方法中的容量缩放优化）

题目描述
最大流问题旨在从源点（s）到汇点（t）的网络中找出可传输的最大流量。网络由有向图表示，每条边有容量限制。Ford-Fulkerson方法通过反复寻找增广路径来逐步增加流量，但基础版本可能因路径选择不当而效率低下（例如，边容量为无理数时可能无法终止）。容量缩放（Capacity Scaling）优化通过优先处理高容量边，确保算法在多项式时间内运行。

解题过程

1. 核心思想
   容量缩放引入一个缩放参数Δ，初始时设为小于等于最大容量的2的幂（如Δ = 2^⌊log₂(max capacity)⌋）。在每轮迭代中，仅考虑剩余容量≥Δ的边，构建“Δ-残差图”，并寻找增广路径。当无法找到更多路径时，Δ减半，重复过程直至Δ=0。

2. 算法步骤

   • 步骤1：初始化
     设流量f初始为0，计算初始Δ = 2^k，其中k为满足2^k ≤ 最大边容量的最大整数。
   • 步骤2：缩放阶段（Δ > 0）
     在当前Δ下，执行以下循环：
     • 构建Δ-残差图：仅保留剩余容量≥Δ的边。
     • 在Δ-残差图中用BFS/DFS寻找从s到t的增广路径。
     • 若存在路径，沿路径推送流量（流量值为路径上最小剩余容量），更新残差图。
     • 若不存在路径，将Δ减半（Δ ← Δ/2）。
   • 步骤3：终止条件
     当Δ=0时，算法结束，当前流量f即为最大流。

3. 示例说明
   假设网络边容量为[0, 10]，初始Δ=8（因8=2³≤10）。

   • Δ=8时：仅处理剩余容量≥8的边。若找到路径，推送流量并更新残差图；否则Δ减半为4。
   • Δ=4时：重复上述过程，逐步缩小Δ至0。
     通过优先处理高容量边，减少低效增广次数，将复杂度优化至O(E² log U)（U为最大容量）。

4. 为什么有效？

   • 每次缩放阶段最多进行O(E)次增广（因每阶段至少推送Δ流量）。
   • 缩放阶段数为O(log U)，总增广次数受限，避免基础Ford-Fulkerson的缺陷。

总结
容量缩放通过“由粗到精”的缩放策略，优先利用高容量边，显著提升搜索效率，确保算法在任意容量下均可靠收敛。