最大流问题（Capacity Scaling 优化）

字数 1198 2025-11-12 02:22:03

最大流问题（Capacity Scaling 优化）

题目描述：给定一个有向图，其中每条边有一个容量（非负整数），以及一个源点和一个汇点，求从源点到汇点的最大流。Capacity Scaling 是一种优化方法，通过逐步考虑边容量的最高位到最低位，在残量图中寻找增广路径，以提高算法效率。

解题步骤：

理解基本概念
- 流网络：有向图 G=(V,E)，每条边 (u,v) 有容量 c(u,v)≥0
- 流函数 f: V×V→R 满足：
  - 容量约束：0≤f(u,v)≤c(u,v)
  - 流量守恒：除源点 s 和汇点 t 外，每个顶点流入流出相等
- 最大流：从 s 到 t 的最大流量值
Capacity Scaling 核心思想
- 引入缩放参数 Δ，初始为不大于最大容量的最大 2 的幂
- 只考虑残量图中容量 ≥Δ 的边
- 随着算法进行，逐步将 Δ 减半，直到 Δ=0
算法详细步骤
- 步骤 1：初始化
  - 设置流 f 为全 0
  - 找到最大容量 C = max{c(u,v)}
  - 设置 Δ = 2^⌊log₂C⌋（不大于 C 的最大 2 的幂）
- 步骤 2：外层循环（缩放阶段）
  - 当 Δ ≥ 1 时执行：
    a. 在残量图 G_f(Δ) 中，只保留残量容量 ≥Δ 的边
    b. 在 G_f(Δ) 中寻找增广路径
    c. 如果找到增广路径，沿路径推送尽可能多的流
    d. 如果找不到增广路径，将 Δ 减半
- 步骤 3：内层循环（寻找增广路径）
  - 在当前的 G_f(Δ) 中，使用 BFS 或 DFS 寻找 s 到 t 的路径
  - 如果找到路径 P，计算路径上的最小残量容量：
    min_residual = min{r(u,v) | (u,v) ∈ P}
  - 沿路径 P 推送 min_residual 的流量
  - 更新残量图：对于路径上的每条边 (u,v)
    - f(u,v) = f(u,v) + min_residual
    - f(v,u) = f(v,u) - min_residual（反向边）
算法终止
- 当 Δ=0 时，算法结束
- 此时的流 f 就是最大流
时间复杂度分析
- 外层循环执行 O(logC) 次
- 每次缩放阶段最多有 O(m) 次增广
- 每次增广需要 O(m) 时间
- 总时间复杂度：O(m²logC)
算法优势
- 相比基本的 Ford-Fulkerson 方法，避免了选择不佳增广路径的问题
- 相比 Edmonds-Karp 算法，在某些情况下更高效
- 特别适合边容量差异较大的情况
实例演示
考虑一个简单网络：
- 顶点：s, a, b, t
- 边：s→a(3), s→b(2), a→b(1), a→t(2), b→t(3)
- 初始 Δ=2（最大容量为3）
- 逐步执行算法，观察流量增长和 Δ 的变化

通过这种逐步缩放的方式，Capacity Scaling 算法能够更系统地探索高容量的增广路径，提高算法效率，特别适合处理容量范围较大的网络流问题。

最大流问题（Capacity Scaling 优化）题目描述：给定一个有向图，其中每条边有一个容量（非负整数），以及一个源点和一个汇点，求从源点到汇点的最大流。Capacity Scaling 是一种优化方法，通过逐步考虑边容量的最高位到最低位，在残量图中寻找增广路径，以提高算法效率。解题步骤：理解基本概念流网络：有向图 G=(V,E)，每条边 (u,v) 有容量 c(u,v)≥0 流函数 f: V×V→R 满足：容量约束：0≤f(u,v)≤c(u,v) 流量守恒：除源点 s 和汇点 t 外，每个顶点流入流出相等最大流：从 s 到 t 的最大流量值 Capacity Scaling 核心思想引入缩放参数 Δ，初始为不大于最大容量的最大 2 的幂只考虑残量图中容量 ≥Δ 的边随着算法进行，逐步将 Δ 减半，直到 Δ=0 算法详细步骤步骤 1：初始化设置流 f 为全 0 找到最大容量 C = max{c(u,v)} 设置 Δ = 2^⌊log₂C⌋（不大于 C 的最大 2 的幂）步骤 2：外层循环（缩放阶段）当 Δ ≥ 1 时执行： a. 在残量图 G_ f(Δ) 中，只保留残量容量 ≥Δ 的边 b. 在 G_ f(Δ) 中寻找增广路径 c. 如果找到增广路径，沿路径推送尽可能多的流 d. 如果找不到增广路径，将 Δ 减半步骤 3：内层循环（寻找增广路径）在当前的 G_ f(Δ) 中，使用 BFS 或 DFS 寻找 s 到 t 的路径如果找到路径 P，计算路径上的最小残量容量： min_ residual = min{r(u,v) | (u,v) ∈ P} 沿路径 P 推送 min_ residual 的流量更新残量图：对于路径上的每条边 (u,v) f(u,v) = f(u,v) + min_ residual f(v,u) = f(v,u) - min_ residual（反向边）算法终止当 Δ=0 时，算法结束此时的流 f 就是最大流时间复杂度分析外层循环执行 O(logC) 次每次缩放阶段最多有 O(m) 次增广每次增广需要 O(m) 时间总时间复杂度：O(m²logC) 算法优势相比基本的 Ford-Fulkerson 方法，避免了选择不佳增广路径的问题相比 Edmonds-Karp 算法，在某些情况下更高效特别适合边容量差异较大的情况实例演示考虑一个简单网络：顶点：s, a, b, t 边：s→a(3), s→b(2), a→b(1), a→t(2), b→t(3) 初始 Δ=2（最大容量为3）逐步执行算法，观察流量增长和 Δ 的变化通过这种逐步缩放的方式，Capacity Scaling 算法能够更系统地探索高容量的增广路径，提高算法效率，特别适合处理容量范围较大的网络流问题。