通用 Dinic 最大流板子#include bits/stdc.h using namespace std; const int N 10005; // 点的数量上限 const int M 200005; // 边的数量上限记得 *2因为要建反向边 const int INF 0x3f3f3f3f; struct Edge { int to, cap, rev; // 终点残量反向边编号 }; vectorEdge g[N]; int depth[N], cur[N]; /* 加边正反两条 */ void add(int u, int v, int cap) { g[u].push_back({v, cap, (int)g[v].size()}); g[v].push_back({u, 0, (int)g[u].size() - 1}); } /* BFS 建层 */ bool bfs(int s, int t) { fill(depth, depth N, -1); queueint q; depth[s] 0; q.push(s); while (q.size()) { int u q.front(); q.pop(); for (auto e : g[u]) { // 注意这里的 if (e.cap 0 depth[e.to] -1) { depth[e.to] depth[u] 1; q.push(e.to); } } } return depth[t] ! -1; } /* DFS 多路增广 */ int dfs(int u, int t, int f) { if (u t) return f; for (int i cur[u]; i g[u].size(); i) { Edge e g[u][i]; // 关键引用直接改原图 if (e.cap 0 depth[e.to] depth[u] 1) { int flow dfs(e.to, t, min(f, e.cap)); if (flow 0) { e.cap - flow; // 正向边减少 g[e.to][e.rev].cap flow; // 反向边增加 return flow; } } } return 0; } /* Dinic 主函数 */ int dinic(int s, int t) { int flow 0; while (bfs(s, t)) { fill(cur, cur N, 0); while (int f dfs(s, t, INF)) { flow f; } } return flow; }用法示例例题P3376【模板】网络最大流洛谷int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, s, t; cin n m s t; for (int i 0; i m; i) { int u, v, w; cin u v w; add(u, v, w); } cout dinic(s, t) \n; return 0; }板子记忆建图 add分层 bfs送水 dfs主循环 dinic关键三处少一个都可能 WA位置为什么for (auto e : g[u])防止 BFS 误拷贝int i cur[u]当前弧优化Edge e g[u][i]核心改原图残量注意事项N 开够点编号从 1 开始也要保证N max_vertexM 要 ×2因为每条边要建一条反向边多测记得清空for (int i 1; i n; i) g[i].clear();INF 不要开太大0x3f3f3f3f足够且不容易溢出讲解一、怎么存图残量网络边的结构struct Edge { int to; // 这条边指向谁 int cap; // 剩余容量残量 int rev; // 反向边在 to 的邻接表中的下标 };这是什么意思网络流必须支持“反悔”。比如你给u→v流了 5 单位以后你可能想退回去一点。所以我们每条边都配一条反向边正向边cap 剩余容量反向边cap 已流流量rev的作用是快速找到反向边在哪。邻接表存图vectorEdge g[N];g[u]里存的是u 的所有出边。加边函数最重要void add(int u, int v, int cap) { g[u].push_back({v, cap, (int)g[v].size()}); // 正向边 g[v].push_back({u, 0, (int)g[u].size() - 1}); // 反向边 }逐行解释g[u].push_back({v, cap, (int)g[v].size()});从u到v容量是cap反向边在g[v]的第g[v].size()个位置g[v].push_back({u, 0, (int)g[u].size() - 1});反向边容量为 0一开始没流反向边的rev指向刚刚加的正向边以后只要e.cap - f同时g[e.to][e.rev].cap f就完成了“反悔”二、BFS给图“分层”int depth[N]; bool bfs(int s, int t) { fill(depth, depth N, -1); queueint q; depth[s] 0; q.push(s); while (q.size()) { int u q.front(); q.pop(); for (auto e : g[u]) { if (e.cap 0 depth[e.to] -1) { depth[e.to] depth[u] 1; q.push(e.to); } } } return depth[t] ! -1; }这段代码在干嘛depth[v]从源点 s 到 v 的最短距离按边数depth[v] -1表示这个点还没访问到e.cap 0只走还能流的边如果depth[t] -1说明 s 到 t 已经不连通了算法结束三、DFS在分层图上“送水”当前弧数组int cur[N];cur[u]记录u 这个节点我已经尝试到第几条边了DFS 主体int dfs(int u, int t, int f) { if (u t) return f; for (int i cur[u]; i g[u].size(); i) { Edge e g[u][i]; if (e.cap 0 depth[e.to] depth[u] 1) { int ret dfs(e.to, t, min(f, e.cap)); if (ret 0) { e.cap - ret; g[e.to][e.rev].cap ret; return ret; } } } return 0; }一行一行拆if (u t) return f;到了终点直接返回能送的水量for (int i cur[u]; i g[u].size(); i)关键cur[u]是引用修改它会直接保存进度下次再来 u不会从头扫边if (e.cap 0 depth[e.to] depth[u] 1)只走还有容量并且严格向下一层走防止绕圈int ret dfs(e.to, t, min(f, e.cap));能送的水 当前限制f和 边容量e.cap的最小值if (ret 0) { e.cap - ret; // 正向边减 g[e.to][e.rev].cap ret; // 反向边加 return ret; }完成一次增广立刻返回一次 DFS 只送一条增广路但因为有while (dfs(...))会反复调用直到送不动四、Dinic 主函数把一切串起来int dinic(int s, int t) { int flow 0; while (bfs(s, t)) { // 只要还能分层 fill(cur, cur N, 0); // 每一轮重置当前弧 while (int f dfs(s, t, INF)) { flow f; // 累加流量 } } return flow; }这里发生了什么BFS 建层DFS 多路增广阻塞流重复直到无法到达 t 每一轮 BFS 后dfs会被反复调用直到当前分层图被“堵死”。五、一张“对照表”代码 vs 现实代码现实含义Edge::cap水管还能流多少Edge::rev反悔用的反向水管depth[]城市在第几站bfs画地图、编号dfs送水工出发cur[]送水工的小本子while(dfs)把这一层水送干