Dinic 比 Edmonds–Karp 快，因其通过 BFS 构建分层图后，DFS 多次增广求阻塞流，均摊效率更高；需正确实现层级检查、当前弧优化、成对边存储及 long long 溢出防护。
为什么 Dinic 比 Edmonds–Karp 快？关键在分层图和阻塞流
因为 Dinic 不是每次 BFS 找一条增广路就重来，而是先建一层「允许走的边」（即残量 > 0 且层级严格 +1），再在这个分层图里 DFS 尽可能多退多进——这叫阻塞流。一次 BFS 配多次 DFS，均摊下来快得多。
常见错误是：BFS 后没检查 level[t] == -1 就直接 DFS，导致死循环或越界访问；或者 DFS 时没用引用传参 int& flow，导致流量没真正扣减。
- 分层图只在 BFS 成功后构建，失败说明已无增广路，直接退出
-
DFS必须支持「当前弧优化」：用ptr[u]记录节点u上次试过的边索引，避免重复扫已满流的边 - 层级数组
level[]和当前弧数组ptr[]都得每轮 BFS 前重置
Dinic 的核心结构怎么组织？别把边存成 vector<edge></edge>
边必须成对存储（正向边 + 反向边），索引差为 1，这样 rev(i) = i ^ 1 才能快速定位反向边。用 vector<vector>> g</vector> 存邻接表，但表里只放边的索引，不是边本身。
典型翻车点：手写 add_edge(u, v, cap) 时忘了把反向边容量设为 0；或者调用 DFS(u, flow) 时传入了原始 cap 而不是剩余容量 res，导致超流。
立即学习“C++免费学习笔记（深入）”；
- 每加一条边，调用两次
edges.push_back({v, cap, (int)edges.size() + 1})和edges.push_back({u, 0, (int)edges.size() - 1}) -
g[u].push_back(edges.size() - 2)，g[v].push_back(edges.size() - 1) - DFS 中更新残量要同步改正向边和反向边：
edges[i].cap -= f; edges[edges[i].rev].cap += f
什么时候该用 long long？别等 WA 了才改
最大流值可能远超 int：比如 1e4 个点、每条边容量 1e9，总流轻松破 1e13。但更隐蔽的问题是 DFS 中临时变量如 flow、f、累加的 ret，只要中间参与过乘法或大值相加，就得全程 long long。
编译器不会报错，但溢出后变成负数或小正数，结果完全不可预测。本地小数据跑得通，一交就 WA 是最典型的症状。
-
edges结构体里的cap字段必须是long long -
BFS中的队列元素、DFS参数和返回值、主循环里的max_flow全部用long long - 连
memset(level, -1, sizeof level)都得确认level数组类型匹配，否则清零异常
模板里最容易漏掉的三处初始化
不是所有变量都在函数开头显式赋值。漏掉任意一个，轻则答案偏小，重则运行时崩溃。
比如 ptr[] 不重置，某次 DFS 会从上一轮残留位置开始扫，跳过本该尝试的边；level[] 不清空，BFS 可能误判可达性；edges.clear() 忘了调，旧边还在，新图混着旧数据跑。
- 每次跑新图前：调用
edges.clear()，for (int i = 0; i - BFS 前：
memset(level, -1, sizeof level)或fill(level, level + n + 1, -1) - DFS 前：
fill(ptr, ptr + n + 1, 0)—— 这个漏得最多
复杂点不在算法逻辑，而在这些状态变量的生命周期管理。边界稍一松动，整个流就断了。
