最大流问题（Capacity Scaling 优化）
题目描述：给定一个有向图G=(V,E)，其中每条边(u,v)∈E有一个非负容量c(u,v)≥0。指定源点s和汇点t。Capacity Scaling算法是Ford-Fulkerson方法的一种优化版本，通过逐步处理不同数量级的容量来提高效率。该算法从处理最高位容量开始，逐步细化，避免在残余网络中反复寻找增广路径。
解题过程：
-
算法核心思想
Capacity Scaling的核心洞察是：优先处理容量较大的边，通过"容量缩放参数Δ"来控制系统性地探索增广路径。算法从最大容量级别开始（Δ=2^⌊log₂C⌋，其中C是最大边容量），只考虑容量≥Δ的边，逐步将Δ减半直到Δ<1。 -
算法步骤
步骤1：初始化
- 设置初始流f为0流（所有边流量为0）
- 计算最大容量C = max{c(u,v) | (u,v)∈E}
- 设置初始缩放参数Δ = 2^⌊log₂C⌋（不大于C的最大2的幂）
步骤2：容量缩放阶段（当Δ ≥ 1时循环）
a) 构建Δ-残余图：只包含残余容量≥Δ的边
b) 在Δ-残余图中寻找s-t增广路径
c) 如果找到增广路径，沿路径推送流量（推送量为路径上最小残余容量）
d) 如果找不到增广路径，将Δ减半：Δ = Δ/2
步骤3：当Δ < 1时算法结束，返回最大流f
- 详细执行过程
以具体图例说明：有向图包含顶点{s,a,b,t}，边容量为：
s→a: 12, s→b: 14, a→b: 7, a→t: 10, b→t: 11
初始化阶段：
- C = max{12,14,7,10,11} = 14
- Δ = 2^⌊log₂14⌋ = 2^3 = 8（因为8≤14<16）
第一缩放阶段（Δ=8）：
构建Δ-残余图（只含容量≥8的边）：
s→a(12≥8), s→b(14≥8), a→t(10≥8), b→t(11≥8)
寻找增广路径：s→a→t，推送流量min(12,10)=10
更新流量：s→a:10, a→t:10
第二缩放阶段（Δ=4）：
构建Δ-残余图（容量≥4）：
包含所有边，因为最小容量7≥4
寻找增广路径：s→b→t，推送流量min(14,11)=11
更新流量：s→b:11, b→t:11
继续在Δ=4下寻找：路径s→a→b→t，推送流量min(2,7,1)=2
（a→b残余容量7，b→t残余容量0但反向边容量11）
-
算法正确性分析
Capacity Scaling本质仍是Ford-Fulkerson方法，因此正确性由最大流最小割定理保证。关键改进在于：通过Δ控制每次只处理"重要"的边，避免在低容量边上浪费时间。 -
复杂度分析
- 缩放阶段数：O(log₂C)
- 每个缩放阶段最多找O(m)条增广路径
- 总复杂度：O(m²log₂C)，优于基础Ford-Fulkerson的O(mC)
- 实际应用优化
在实际实现中，可用BFS/DFS寻找增广路径。当Δ较大时，图较稀疏，搜索效率高；Δ变小时，虽然图变稠密，但需要推送的流量也变小。
这种缩放思想可推广到其他图算法，是处理数值型问题的通用优化技术。