基于“按边数最短的增广路”反复 BFS 寻找并增广的最大流算法，复杂度有保证，适合作为稳健基线与教学实现。
Description: Flow algorithm with guaranteed complexity . To get edge flow values, compare capacities before and after, and take the positive values only. Status: stress-tested
-
定义与背景
- 目标：在容量非负的有向网络 G=(V,E) 中，从源 s 向汇 t 发送最大可能的流量。
- 残量网络：每条有向边 (u,v) 维护剩余容量 c(u,v) 与反向边 c(v,u)，用于回退/调整已发送流量。
- Edmonds–Karp（EK）：特化的 Ford–Fulkerson，规定每轮用队列 BFS 在残量网络中寻找“边数最少”的增广路，再按该路的瓶颈容量增广。
-
典型适用场景
- 需要复杂度“有明确上界保证”的基线实现。
- 规模中小、边较稀疏的通用最大流/最小割问题；或用于验证其他更快算法的正确性。
-
接口/数据结构（据实现习惯）
- 签名：template
T edmondsKarp(graph, source, sink) - graph：邻接结构，保存对每条边的当前残量；常见为邻接表 + 反向边索引或哈希映射（原注有“比较容量前后得边流量”的提示）。
- source/sink：源/汇点索引。
- 返回：最大流值（类型 T）。
- BFS 辅助：
- par[]：记录前驱（及边索引）以便回溯增广路；
- dist[]（可选）：按边数层次；队列保证最短路径性质。
- 签名：template
-
核心流程/要点（BFS 最短增广路）
- 初始化 flow=0。
- 循环执行：
- 在残量网络上自 s 做 BFS，忽略 c(u,v)≤0 的边；若 t 不可达，算法结束。
- 回溯路径 t→s，计算瓶颈 inc = min c(u,v)。
- 沿路径更新残量：c(u,v) -= inc，c(v,u) += inc；flow += inc。
- 结束后 flow 为最大流；最小割侧可由“最后一次 BFS 可达集”给出。
-
获取边流量（原注语义）
- 若需输出每条原始边的实际流量，可在开始时保存原始容量 cap0(u,v)，算法结束后以 cap0(u,v)−c(u,v) 的正部作为该边的流量。
-
复杂度与边界条件
- 时间复杂度：保证 O(VE^2)。直观理由：每条边被标记为“饱和”或“距 s 的最短路边数增加”的次数是可计数的有限次上界。
- 空间复杂度：O(V+E)。
- 多源/多汇：可加超级源/汇并以 0 或所需容量连接。
- 不可达：若 s 与 t 最初即不连通，返回 0。
- 自环/重边：自环无意义应忽略；重边可保留（残量自动叠加）。
- 容量类型与上界：通常为整型/长整型；若使用浮点容量，BFS 路径“最短边数”仍成立，但增广数值需 EPS 比较。
- INF/哨兵：瓶颈初值取类型上限或问题可推导上界；避免溢出。
-
变体/扩展与对比
- 与 057-图论-Dinic最大流：Dinic 每轮在分层图内推“阻塞流”，通常远快于 EK；EK 胜在易实现与复杂度保证简单明了。
- 与 076-图论-PushRelabel：Push-Relabel 在许多密图/随机图表现优秀，代码也精简；EK 适合作为可读性强的教学与基线。
- 与匹配/割：
- 二分图最大匹配可建容量为 1 的网络，用 EK 求得；但更推荐 067-图论-HopcroftKarp 或 Dinic（更快）。
- 最小割集合可由最终残量可达性判定获得；与 074-图论-最小割 概念一致。
- 与最小费用最大流 073-图论-最小费用最大流：EK 不处理费用；当需成本最小时，应切换费用流。
-
正确性要点与不变式
- BFS 最短性不变式：每轮增广使用边数最短的路径；一旦某条边饱和或被反向回退，其在后续 BFS 中的“层次距离”单调不降，保证整体迭代有限。
- 流守恒与容量约束：残量/反向残量成对更新，确保在任意中间状态都满足流的可行性。
- 终止性：当 BFS 不可达 t 时，不存在任何增广路，即达到最大流（max-flow/min-cut 定理）。
-
与相邻技术的取舍建议
- 若追求速度：优先 Dinic 或 Push-Relabel；EK 作为稳健可读的下限参考实现。
- 若需边流量明细：EK 残量差分易于恢复每边流量；Dinic 亦可通过 oc/c 差值恢复。