Dinic比Edmonds-Karp快因其分层图+BFS预处理+多路增广，复杂度O(V²E)优于O(VE²)；需邻接表存边、正反向边成对存储（下标异或1）、当前弧优化防重复扫描。
为什么Dinic比DFS增广路（如Edmonds-Karp）快？
Dinic的核心加速在于「分层图 + 多路增广」：它先用BFS构建以源点为起点的最短路径层次图（level[]数组），再在该图上用DFS一次性找多条阻塞流，避免反复进入死胡同。对稀疏图或单位容量图，复杂度可压到 O(V²E)；实践中常远优于Edmonds-Karp的 O(VE²)，尤其在存在大量短增广路时。
关键结构体怎么写才不爆内存又支持重边？
必须用邻接表存边，且正向边与反向边成对存储（下标异或1），方便快速访问反向边。不要用map或vectoredges里push两次（正向+初始容量为0的反向边）。
struct Edge {
int to, cap, rev; // rev是反向边在edges中的下标
};
vector<Edge> edges;
vector<vector<int>> graph; // graph[u]存从u出发的所有边在edges中的索引
常见错误：
• 忘记初始化rev字段，导致反向边更新错位
• 把graph做成vector<vector>></vector>，导致BFS/DFS中无法O(1)拿到边索引
• 边数组开太小（比如只开m，实际要开2*m）
BFS建分层图时要注意哪些边界？
BFS只走残量 > 0 的边，且只给未访问节点赋level。关键判断是：if (e.cap > 0 && level[e.to] == -1)。漏掉cap > 0会把已满边也纳入层次图；漏掉== -1会导致重复入队甚至死循环。
立即学习“C++免费学习笔记（深入）”；
实用建议：
• 初始化level全为-1，源点level[s] = 0
• BFS结束后若level[t] == -1，说明已无增广路，直接退出主循环
• 不要用queue
DFS找阻塞流为什么必须用当前弧优化？
没优化的DFS会在同一层反复扫描已饱和的边，退化成指数级。当前弧优化（iter[u]）记录每个节点上次成功扩展的边索引，下次从那里继续——本质是“每个点只试一遍所有出边”。
代码片段示意：
int dfs(int u, int t, int f) {
if (u == t) return f;
for (int& i = iter[u]; i < graph[u].size(); i++) {
Edge& e = edges[graph[u][i]];
if (e.cap > 0 && level[u] + 1 == level[e.to]) {
int d = dfs(e.to, t, min(f, e.cap));
if (d > 0) {
e.cap -= d;
edges[e.rev].cap += d;
return d;
}
}
}
return 0;
}
注意：
• iter[u]必须是引用（int&），否则循环内修改不生效
• 每次进入新BFS轮次前，要重置iter数组为0
• 返回0不代表失败，只是当前路径不通，需继续试下一条边（所以不能break）
真正卡住性能的往往不是算法本身，而是建图时边序号混乱、BFS后忘了检查level[t]是否可达、或者DFS里没用引用导致当前弧失效——这几个点调通，Dinic就能稳定跑赢SPFA-based的其他流算法。
