最大流问题（Edmonds-Karp 算法）

题目描述
给定一个有向图，其中每条边有一个非负容量（capacity），以及一个源点（source）和一个汇点（sink），求从源点到汇点的最大流量。流量需满足以下约束：

1. 容量限制：每条边上的流量不能超过其容量。
2. 流量守恒：除源点和汇点外，每个顶点的流入流量等于流出流量。

Edmonds-Karp 算法是 Ford-Fulkerson 方法的一种实现，通过 广度优先搜索（BFS） 寻找增广路径，确保每次找到的增广路径是 最短路径（边数最少），从而保证算法的高效性。

解题过程

1. 基本概念

• 残留网络（Residual Graph）：在原图的基础上，为每条边添加一条反向边，容量初始为 0。当正向边有流量 \(f\) 通过时，正向边容量减少 \(f\)，反向边容量增加 \(f\)。残留网络中的边容量表示该边还能承载的流量。
• 增广路径（Augmenting Path）：在残留网络中，从源点到汇点的一条路径，路径上所有边的容量均大于 0。通过该路径可以增加流量。

2. 算法步骤

• 步骤 1：初始化流量为 0，构建残留网络（初始时与原图相同，反向边容量为 0）。
• 步骤 2：在残留网络中使用 BFS 寻找从源点到汇点的最短路径（边数最少）。
  • 如果找不到路径，算法结束，当前流量即为最大流。
  • 如果找到路径，进入步骤 3。
• 步骤 3：计算路径上的最小容量（瓶颈容量），记为 \(f\)。
  • 将路径上每条正向边的容量减少 \(f\)，反向边容量增加 \(f\)。
  • 总流量增加 \(f\)。
• 步骤 4：重复步骤 2 和 3，直到无法找到增广路径。

3. 举例说明
假设有下图（边上的数字表示容量）：

    A --3--> B
  /           \
s               t
  \           /
    C --5--> D

源点 \(s\)，汇点 \(t\)，边：\(s \to A\)（容量 3），\(s \to C\)（容量 5），\(A \to B\)（容量 3），\(C \to D\)（容量 5），\(B \to t\)（容量 3），\(D \to t\)（容量 5）。

迭代 1：

• BFS 找到路径 \(s \to A \to B \to t\)，瓶颈容量为 3。
• 更新流量：路径上的边容量减少 3，反向边容量增加 3。
• 当前总流量 = 3。

迭代 2：

• BFS 找到路径 \(s \to C \to D \to t\)，瓶颈容量为 5。
• 更新流量，总流量变为 8。

迭代 3：

• 残留网络中无法找到从 \(s\) 到 \(t\) 的路径，算法结束。
• 最大流 = 8。

4. 为什么使用 BFS？

• BFS 保证每次找到的增广路径是最短路径，避免 Ford-Fulkerson 在某些情况下陷入低效（如边容量为无理数时）。
• 时间复杂度为 \(O(V E^2)\)，其中 \(V\) 是顶点数，\(E\) 是边数。

5. 关键点

• 反向边允许“撤销”流量，为后续增广路径提供调整机会。
• 算法终止时，最小割的容量等于最大流（最大流最小割定理）。

通过以上步骤，Edmonds-Karp 算法能高效求解最大流问题。