xxx 最大流问题（Ford-Fulkerson 方法中的 Edmonds-Karp 算法） 题目描述 给定一个有向图，其中每条边有一个非负容量（capacity），以及两个特殊节点：源点（source）和汇点（sink）。最大流问题的目标是找出从源点到汇点的最大流量，使得每条边上的流量不超过其容量，且除源点和汇点外，每个节点的流入流量等于流出流量（流量守恒）。 解题过程 Edmonds-Karp 算法是 Ford-Fulkerson 方法的一种实现，它使用 BFS（广度优先搜索）来寻找增广路径，确保每次选择的是最短路径（边数最少）。其核心步骤包括： 初始化 将所有边的初始流量设为 0。 构建残量图（residual graph），初始时残量图的边容量与原图相同。 重复寻找增广路径 在残量图中，使用 BFS 从源点 \( s \) 到汇点 \( t \) 寻找一条路径，其中每条边的残量（剩余容量）均大于 0。 若找不到路径，算法结束；当前总流量即为最大流。 若找到路径，记录路径上的最小残量 \( \text{min\_capacity} \)，即路径上边的最小剩余容量。 更新流量与残量图 沿增广路径的每条边增加流量 \( \text{min\_capacity} \)。 同步更新残量图： 对于路径上的每条边 \( (u, v) \)，其残量减少 \( \text{min\_capacity} \)（表示剩余容量减少）。 同时，反向边 \( (v, u) \) 的残量增加 \( \text{min\_capacity} \)（允许后续流量回退）。 终止条件 当无法找到新的增广路径时，算法终止。此时从源点流出的总流量即为最大流。 为什么有效？ BFS 保证每次找到的增广路径是最短的，避免 Ford-Fulkerson 在特定情况下陷入无限循环。 残量图中的反向边允许“撤销”之前的流量分配，确保算法能探索更优的流量分配方案。 时间复杂度为 \( O(V E^2) \)，其中 \( V \) 是顶点数，\( E \) 是边数。 示例 假设有一个简单图：边 \( s \to a \)（容量 3）、\( a \to t \)（容量 2）、\( s \to b \)（容量 2）、\( b \to t \)（容量 3）。 第一次 BFS 可能找到路径 \( s \to a \to t \)，最小残量 2，更新流量后残量图中 \( s \to a \) 残量变为 1，\( a \to t \) 残量变为 0，并增加反向边容量。 第二次 BFS 找到路径 \( s \to b \to t \)，最小残量 2，更新后得到总流量 4。 第三次 BFS 可能找到路径 \( s \to a \to b \to t \)（利用反向边 \( a \to b \) 允许流量从 \( a \) 回退到 \( b \)），最小残量 1，总流量变为 5，此时无更多增广路径，算法终止。 通过逐步调整残量图，Edmonds-Karp 算法能高效且可靠地找到最大流。