不能真建分层图结构，因为会破坏反向边索引、当前弧优化及残留网络更新；分层本质是基于level[]数组的动态访问规则，bfs需满足残量>0、目标未标记、源点level为0三条件。
分层图不是显式构造的，而是用 bfs 打标层级后，在 dfs 中靠 level[v] == level[u] + 1 动态约束实现的。 直接建新图不仅浪费空间，还会破坏当前弧优化和残留网络更新逻辑。
为什么不能真建一个分层图结构？
常见误解是以为要新建一张只含跨层边的图。实际完全没必要——Dinic 的分层本质是“访问许可规则”，不是物理图结构。
- 每次
bfs后，level[]数组已隐含全部分层信息； -
dfs过程中只要检查level[e.to] == level[u] + 1就等价于“只走分层图中的边”； - 若真复制边建新图，
addEdge时的反向边索引（rev）会错乱，flow更新失效； - 当前弧优化（
ptr[]）依赖原邻接表顺序，换图就断了。
bfs 分层时必须满足的三个条件
bfs 不是简单遍历，它决定哪些边“在当前阶段可参与增广”。漏掉任一条件都会导致漏路径或死循环：
- 边必须有剩余容量：
e.flow （即 <code>e.cap - e.flow > 0）； - 目标节点未被标记层级：
level[e.to] == -1（避免重复入队和环）； - 源点
s的level[s]必须初始化为0，否则后续level[v] == level[u] + 1全部失效。
错误写法示例：if (e.cap > 0 && level[e.to] == -1) —— 忘了判断是否还有残量，会把已饱和但未更新的边误判为可用。
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
dfs 增广时如何保证只走分层图路径？
关键就在循环体内的层级校验和当前弧推进逻辑：
for (int& i = ptr[u]; i 0) {
e.flow += pushed;
graph[e.to][e.rev].flow -= pushed;
return pushed;
}
}
}
注意两点：
- 必须写成
level[e.to] == level[u] + 1，不能是>=或，否则退化为 DFS 暴搜； - 必须同时检查
e.flow ，因为 <code>bfs阶段之后残留网络可能已变化（其他dfs改了流量），仅靠层级不够； -
ptr[u]是引用绑定（int& i = ptr[u]），确保同一节点多次dfs调用间不重复扫已试过的边。
容易被忽略的边界：汇点未被分层就提前退出
bfs 返回 false 的唯一可靠依据是 level[t] == -1，而不是“队列空了”或“没找到任何新点”。如果忘记这步判断，while(bfs(s,t)) 会无限循环在空分层上。
典型疏漏：return !q.empty() —— 错！队列空不代表汇点可达，只代表 BFS 暂停；正确写法只能是 return level[t] != -1。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
