学习目标
前置知识与环境
先阅读网络流与二分图匹配。需要 C++17 编译器，运行前可执行 make doctor。
题目
有向网络中每条边有非负容量。求从 s 到 t 的最大流。允许原图同一方向的平行边和两方向各自独立的边；每条输入边都必须拥有自己的残量反向边。使用 BFS 在残量网络中寻找边数最少的增广路。
输入格式
第一行 n m s t，随后 m 行 u v capacity。编号 1..n，2 ≤ n ≤ 200，0 ≤ m ≤ 5000，s≠t，u≠v，0 ≤ capacity ≤ 2×10^9。
输出格式
一行最大流量，使用 64 位整数。s 与 t 不连通输出 0。
样例输入
input
4 4 1 4
1 2 3
1 3 2
2 4 2
3 4 4样例输出
output
4样例解释
经顶点 2 和 3 的两条通道分别传送 2 单位流量，总流量为 4；任何额外流量都会超过某条通道的瓶颈容量。
任务
- 为每条输入边添加容量为 0 的独立反向边。
- BFS 记录父顶点与父边下标。
- 沿路取瓶颈，更新正反容量并累计流量。
在 student/main.cpp 的 TODO 处完成算法。起始代码可以编译，但不代表已经实现题目；参考实现位于 solution/main.cpp。
正常、边界与错误情况
反向残量边用于撤销旧流量；不能把原图已有的反向输入边当成它。
输入保证符合上述格式与范围，不要求处理损坏输入。无解、不可达等情况按本题输出合同处理，不视为格式错误。测试点包含如下场景，每点 5 分，共 100 分：
| 测试点 | 类型 |
|---|---|
001-sample | 样例 |
002-no-edges | 边界 |
003-zero-capacity | 边界 |
004-parallel-edges | 易错反例 |
005-opposite-input-edges | 易错反例 |
006-reverse-residual-required | 易错反例 |
007-large-flow | 易错反例 |
008-non-default-terminals | 易错反例 |
009-seeded-network-0 | 正常 |
010-seeded-network-1 | 正常 |
011-seeded-network-2 | 正常 |
012-seeded-network-3 | 正常 |
013-seeded-network-4 | 正常 |
014-seeded-network-5 | 正常 |
015-seeded-network-6 | 正常 |
016-seeded-network-7 | 正常 |
017-seeded-network-8 | 正常 |
018-long-chain | 规模 |
019-many-channels | 规模 |
020-dense-forward | 规模 |
运行与评分
在本 Lab 目录执行：
powershell
make doctor
make run CASE=001-sample
make score未安装 Make 时，在仓库根目录执行：
powershell
pnpm lab:doctor -- labs/chapter-07/exercise/E-07-29-edmonds-karp
pnpm lab:run -- labs/chapter-07/exercise/E-07-29-edmonds-karp --case 001-sample
pnpm lab:score -- labs/chapter-07/exercise/E-07-29-edmonds-karp解题思路
为每条输入边建立独立的正向边和反向残量边。每轮 BFS 找到最短增广路，沿路计算瓶颈并更新正反向容量，直到不存在从源点到汇点的残量路径。
复杂度分析
Edmonds-Karp 时间 O(n·m²)，空间 O(n+m)。这是教学规模的模板，容量很大时也不应逐单位增广。
完成清单
思考与复盘
- 本题最容易遗漏的约束是什么？
参考思路
反向残量边用于撤销旧流量；不能把原图已有的反向输入边当成它。
- 为什么每条输入边都必须有独立的反向残量边？如果把平行边合并，哪种重新分配流量的情况会出错？
参考思路
反向边用于撤销此前经过的流量；平行边各自容量和流量独立，合并会丢失它们的身份，导致残量网络无法准确表示可撤销的流量。