xxx 最大流问题（Edmonds-Karp算法） 题目描述 最大流问题（Maximum Flow Problem）是图论中的经典问题，通常这样描述： 给定一个有向图 \( G = (V, E) \)，其中每条边 \( (u, v) \in E \) 有一个非负容量 \( c(u, v) \geq 0 \)。 指定两个特殊节点：源点 \( s \) 和汇点 \( t \)。 目标是找到从 \( s \) 到 \( t \) 的最大流量，满足以下约束： 容量约束 ：每条边上的流量不能超过其容量。 流量守恒 ：除 \( s \) 和 \( t \) 外，每个节点的流入流量等于流出流量。 解题过程 Edmonds-Karp算法是Ford-Fulkerson方法的一种实现，使用BFS（广度优先搜索）寻找增广路径，确保找到的路径是最短路径（按边数计算），从而保证算法效率。 步骤1：初始化残量图 初始时，残量图与原始图相同，每条边 \( (u, v) \) 的残量容量 \( r(u, v) = c(u, v) \)。 所有反向边 \( (v, u) \) 的初始残量容量 \( r(v, u) = 0 \)（若反向边不存在，则视为容量0的边）。 总流量初始化为0。 步骤2：循环寻找增广路径 重复以下过程直到无法找到增广路径： 使用BFS在残量图中找一条从 \( s \) 到 \( t \) 的路径 ： 要求路径上每条边的残量容量 \( r(u, v) > 0 \)。 BFS保证找到的路径是边数最少的最短路径，避免Ford-Fulkerson中可能出现的低效情况。 计算路径的瓶颈容量 ： 找到路径中所有边的最小残量容量，记为 \( \Delta = \min\{ r(u, v) \mid (u, v) \in \text{路径} \} \)。 更新残量图 ： 对于路径上的每条边 \( (u, v) \)： 减少正向边的残量容量：\( r(u, v) \leftarrow r(u, v) - \Delta \)。 增加反向边的残量容量：\( r(v, u) \leftarrow r(v, u) + \Delta \)。 反向边允许“撤销”流量，确保算法能调整之前的流量分配。 增加总流量 ：将 \( \Delta \) 加到总流量中。 步骤3：终止与输出 当BFS无法找到从 \( s \) 到 \( t \) 的路径时，算法终止。此时的总流量即为最大流。 关键点说明 残量图的作用 ：通过反向边记录“可回收”的流量，确保算法能逐步优化流量分配。 BFS的优势 ：每次找最短路径保证算法在 \( O(VE^2) \) 时间内完成（\( V \) 为顶点数，\( E \) 为边数），避免陷入无限循环。 最大流最小割定理 ：算法结束时，残量图中从 \( s \) 可达的节点构成最小割，其容量等于最大流。 示例 考虑一个简单网络： 边及容量：\( s \to a \)（容量3），\( s \to b \)（容量2），\( a \to b \)（容量1），\( a \to t \)（容量2），\( b \to t \)（容量3）。 执行Edmonds-Karp算法： 第一轮BFS路径 \( s \to a \to t \)，瓶颈容量2，更新残量图。 第二轮BFS路径 \( s \to b \to t \)，瓶颈容量2，更新残量图。 第三轮BFS路径 \( s \to a \to b \to t \)，瓶颈容量1，更新残量图。 无法再找到路径，总流量为 \( 2 + 2 + 1 = 5 \)。 通过逐步调整残量图，算法最终找到最大流为5。