基于分层图与阻塞流的最大流算法：每轮以 BFS 建层、DFS 仅在分层图上推流，直到无法再增广为止。
Description: Flow algorithm with complexity where . O(\min(E^{1/2}, V^{2/3})E) if ; O(\sqrt{V}E) for bipartite matching.
-
定义与背景
- 问题：在有向网络 G=(V,E) 上，容量 cap(u,v)≥0，求从源 s 到汇 t 的最大可达流量。
- 残量网络：对每条边维护剩余容量 c；反向边容量表示可回退的流量。
- 分层图：对残量网络做从 s 出发的 BFS，按最短距离分层，仅保留从低层到高层（层数+1）的边。
-
典型适用场景
- 通用最大流/最小割问题；单位容量图、二分图匹配（将边容量设为 1 并连 s→左部、右部→t）。
- 大规模稀疏图下较为稳健；较 EK 有数量级优势。
-
接口/数据结构（据实现习惯）
- Edge: {to, rev, c, oc}，rev 为反向边索引；c 为当前残量，oc 为初始容量（可用于恢复流量或最小割）。
- 存图：vector<vector
> g；每次 addEdge(a,b,c,rcap) 同时加入正反两条边。 - lvl: vi，BFS 得到的层数数组；ptr: vi，当前弧优化指针，避免 DFS 在已无流的边上反复尝试。
-
核心流程/要点
- 构建网络：按需求 addEdge（无向边分解为两条有向边），容量为非负（常用整型/长整型）。
- 主循环 calc(s,t)
- 分层：用 BFS 计算 lvl，使 lvl[s]=0，且仅当存在从 s 到 t 的路径（lvl[t]≥0）才进入该轮增广。
- 推阻塞流：将 ptr 全置 0，连续调用 dfs(s,t,INF) 在分层图上沿“从低层到高层”的路径推流；当 dfs 返回 0，表示这一轮层图已成阻塞流。
- 重建层图：再次 BFS。若 t 不再可达（lvl[t] = -1），算法结束。
- DFS 细节
- 仅沿 lvl[v]+1 的边尝试；沿边成功推得流 f 后同步减少正向边 c、增加反向边 c。
- 当前弧优化：ptr[v] 从上次停下的边继续，避免重复遍历失败边，显著降低常数。
- 最小割与割侧判定
- 一次最终 BFS 后，lvl[a] 是否被标记可作为“在最小割源侧”的判断（残量网络中从 s 可达的一侧）。
-
复杂度与边界条件
- 复杂度（据原注）：O(VE log U)，单位容量图 O(min(E^{1/2}, V^{2/3})E)，二分图匹配 O(√V·E)。
- 多源/多汇：常以超级源/汇转化，连接 0 容量或要求的一致容量。
- 不可达：若 s 与 t 不连通，首次 BFS 即不可达，返回 0。
- 自环/重边：自环无意义应忽略；重边自动叠加效果，正确性不受影响。
- 容量类型与上界：常用整型/长整型；若使用浮点容量，比较时需 EPS，且“阻塞流”概念会受误差影响。
- INF 与哨兵：dfs(s,t,INF) 的 INF 可取容量上界总和或类型上限；注意防溢出。
-
变体/扩展
- 与 060-图论-EdmondsKarp：EK 每次 BFS 找一条最短增广路，复杂度 O(VE^2)；Dinic 通过“阻塞流”在同一层图内批量推流，通常更快。
- 与 076-图论-PushRelabel：Push-Relabel 在某些密图/极端分布更占优，工程实现也简洁；Dinic 适合稀疏图且便于最小割侧判定。
- 与 073-图论-最小费用最大流：若需要成本最小的最大流或带费用的最小割，应切换到费用流；Dinic 不处理费用维度。
- 与匹配问题：二分图匹配可直接用 Dinic（容量 1），也可用 067-图论-HopcroftKarp 获得更低常数。
-
正确性要点与不变式
- 分层单调性：DFS 仅在 lvl[u]+1→lvl[v] 的边上流动，保证每轮都在最短路径 DAG 上操作。
- 阻塞流：当层图中不存在从 s 到 t 的增广路时，称阻塞；此时任何后续增广必须依赖更长的路径，因而需要重建层图。
- 流量守恒与容量约束：边残量维护与反向边对的更新保证可逆性与守恒；最终达到 max-flow/min-cut 定理的界。
-
与相邻技术对比与取舍建议
- 对比 EK：同为 BFS 参与，但 Dinic 在一轮层图内可多次 DFS 推流，通常数量级加速。
- 对比 Push-Relabel：后者实现简短、局部操作强；Dinic 的“层图+当前弧”在稀疏与单位容量图优势明显。
- 与最小割/割侧：Dinic 结束时，残量可达集天然给出割侧划分，便于下游构造（例如图像分割、割边选择）。