无向图的最大流问题（Edmonds-Karp 算法在有向图中的扩展与应用）
题目描述
给定一个无向图 \(G = (V, E)\) ，其中每条边 \(e\) 有一个整数容量 \(c(e) \ge 0\)。指定一个源点 \(s\) 和一个汇点 \(t\)，求从 \(s\) 到 \(t\) 的最大流。
注意：在无向图中，每条边允许流量双向通过，但流量总和不能超过该边的容量。
示例
无向图：
(2)
/ \
/ \
s---(3)---t
边上的数字为容量，例如边 (s, 2) 容量为 2，边 (2, t) 容量为 2，边 (s, t) 容量为 3。
最大流值是多少？
解题过程循序渐进讲解
第一步：理解无向图最大流与有向图的区别
在有向图中，每条有向边有方向，流量只能从尾部流向头部。
在无向图中，每条边相当于双向都有相同容量的管道。但总流量不能超过容量，这意味着如果在一个方向上流了 \(x\) 单位，另一个方向上就不能流超过 \(c - x\) 单位（否则总流量超过容量）。
关键思路：将无向边转化为两条方向相反的有向边，每条有向边容量等于原无向边的容量。
转化后，我们得到一个有向图，然后应用经典的最大流算法（如 Edmonds-Karp）求解。
第二步：无向边转化为有向边
对于每条无向边 \((u, v)\) 容量 \(c\)：
- 添加有向边 \(u \to v\)，容量 \(c\)。
- 添加有向边 \(v \to u\)，容量 \(c\)。
为什么这样转化是正确的？
假设在无向边上，从 \(u\) 到 \(v\) 流了 \(f_{uv}\)，从 \(v\) 到 \(u\) 流了 \(f_{vu}\)。无向边的限制是：
\[f_{uv} + f_{vu} \le c \]
在转化后的有向图中，有两条有向边：
- 边 \(u \to v\) 上流了 \(f_{uv}\)（正向），其剩余容量为 \(c - f_{uv}\)。
- 边 \(v \to u\) 上流了 \(f_{vu}\)（正向），其剩余容量为 \(c - f_{vu}\)。
注意，如果我们想在 \(u \to v\) 方向增加流量 \(\Delta\)，需要检查有向边 \(u \to v\) 的剩余容量 \(c - f_{uv}\) 是否足够，这与无向边限制 \(f_{uv} + f_{vu} \le c\) 一致。
类似地，在 \(v \to u\) 方向增加流量，检查另一条有向边容量。
因此这种转化完美模拟了无向边的容量约束。
第三步：应用 Edmonds-Karp 算法
Edmonds-Karp 是 Ford-Fulkerson 方法的一种，使用 BFS 寻找最短增广路（按边数最少），复杂度 \(O(VE^2)\)。
在有向图上运行 Edmonds-Karp 的步骤：
- 初始化：创建有向图（如上转化），设置所有边的流量为 0。
- BFS 找增广路：在剩余网络中，从 \(s\) 出发 BFS 寻找一条到 \(t\) 的路径，要求每条边剩余容量 > 0。
- 计算瓶颈容量：在找到的路径上，最小剩余容量值 \(\Delta\) 为该增广路可增加的流量。
- 更新流量：
- 对于路径上的每条有向边 \(u \to v\)，流量增加 \(\Delta\)。
- 同时，反向边 \(v \to u\) 的流量减少 \(\Delta\)（反向边初始容量为 0，流量可为负，表示正向剩余容量增加）。
- 重复步骤 2-4 直到无法找到 \(s\) 到 \(t\) 的增广路。
- 最大流值 = 从 \(s\) 流出的总流量。
注意：反向边的初始容量为 0，但在更新流量时，我们允许减少正向边的流量（通过反向边流“负流量”实现），这是 Ford-Fulkerson 方法的通用技巧，用来撤销之前分配的流量。
第四步：示例计算
示例图（无向）：
顶点：\(s, 2, t\)
边：
- \(e1: (s,2), c=2\)
- \(e2: (2,t), c=2\)
- \(e3: (s,t), c=3\)
转化为有向图：
边：
- \(s \to 2\), cap=2
- \(2 \to s\), cap=2
- \(2 \to t\), cap=2
- \(t \to 2\), cap=2
- \(s \to t\), cap=3
- \(t \to s\), cap=3
初始流量均为 0。
第一次 BFS：可能路径 \(s \to t\)，瓶颈容量 = 3。
更新：
- 边 \(s \to t\) 流量 = 3，剩余容量 = 0。
- 反向边 \(t \to s\) 流量 = -3（相当于剩余容量 3 增加 3 变为 6，但实际我们只记录流量，剩余容量 = 初始容量 - 流量）。
剩余网络（只画剩余容量 >0 的边）：
- \(s \to 2\), res=2
- \(2 \to s\), res=2
- \(2 \to t\), res=2
- \(t \to 2\), res=2
- \(t \to s\), res=3（因为反向边，初始 3 减去流量 -3 得 6，但这里注意：我们通常记录正向边的剩余容量，但算法中直接存流量值然后计算剩余容量）
我们用标准剩余图表示：
- 对边 \(s\to t\) 流量=3，cap=3 → 剩余容量=0，反向边剩余容量=3。
- 对边 \(t\to s\) 是另一条有向边，cap=3，流量=0 → 剩余容量=3。
但为了清晰，我们直接列出所有有向边的剩余容量（res = cap - flow）：
- \(s\to 2\): flow=0, res=2
- \(2\to s\): flow=0, res=2
- \(2\to t\): flow=0, res=2
- \(t\to 2\): flow=0, res=2
- \(s\to t\): flow=3, res=0
- \(t\to s\): flow=0, res=3
第二次 BFS：路径 \(s \to 2 \to t\)：
- \(s\to 2\) res=2
- \(2\to t\) res=2
瓶颈容量 = 2。
更新：
- \(s\to 2\) 流量 += 2 → flow=2, res=0
- \(2\to t\) 流量 += 2 → flow=2, res=0
- 反向边 \(2\to s\) 流量 -= 2 → flow=-2, res=4
- 反向边 \(t\to 2\) 流量 -= 2 → flow=-2, res=4
第三次 BFS：
剩余容量 >0 的边：
- \(2\to s\) res=4
- \(t\to 2\) res=4
- \(t\to s\) res=3
- \(s\to t\) res=0 等
但注意：我们可以走 \(s \to t\) 吗？剩余容量 0，不行。
我们可以走 \(s \to 2\) 吗？剩余容量 0，不行。
从 s 出发没有边到任何点有剩余容量（因为 s 出发的边：s→2 res=0, s→t res=0），所以 BFS 找不到路径，算法停止。
总流量 = 第一次 3 + 第二次 2 = 5。
检查合理性：
原无向图最大流应为：
- 直接边 s-t 流 3
- 路径 s-2-t 流 2
总 5，与算法结果一致。
第五步：算法正确性证明简述
因为我们把无向图转化为有向图后，任何在无向图中的可行流对应到有向图中，可以分配流量到两条有向边上，使得满足容量约束；反之，有向图中找到的流也能映射回无向图，且满足无向边总流量 ≤ 容量。
因此，求转化后有向图的最大流就是原无向图的最大流。
第六步：时间复杂度
转化后边数 \(2|E|\)，所以 \(E' = 2E\)，顶点数 \(V\) 不变。
Edmonds-Karp 复杂度 \(O(VE^2)\) 中的 E 是转化后的有向边数，所以是 \(O(V(2E)^2) = O(VE^2)\)（常数因子忽略）。
最终答案：
无向图最大流可以通过将每条无向边替换为两条相反的有向边，然后使用 Edmonds-Karp 等最大流算法求解，方法与有向图相同。