如果说Ford-Fulkerson是“一条一条地找路找到一条就走一条”的勤劳搬运工那么Dinic算法就是“一次规划好所有路线然后分阶段批量运输”的物流调度专家——它用分层图和当前弧优化将网络流的效率提升到了理论最优的极致。引言你有两个工厂和一个仓库中间是一张错综复杂的管道网络每个管道每秒钟有固定的最大输送量。问题是从工厂到仓库每秒钟最多能输送多少货物这个问题听起来简单但管道网络可能包含成千上万个节点和边你不可能手动去一条条试。网络流算法就是为解决这类“最大输送能力”问题而生的。最朴素的Ford-Fulkerson算法虽然思想直观——不断找增广路并增加流量——但它的时间复杂度取决于流量值在流量很大的情况下会慢到无法接受。Edmonds-Karp算法通过BFS找增广路将复杂度优化到了 O(VE2)O(VE2)但当 VV 和 EE 都达到 104104 级别时仍然捉襟见肘。Dinic算法是网络流算法家族中最耀眼的一颗明星。它在Edmonds-Karp的基础上引入了“分层图”和“当前弧优化”两大杀手锏将时间复杂度优化到了 O(V2E)O(V2E)并且在绝大多数实际场景中表现得远比这个上界要好。如果你只能掌握一种网络流算法那一定是Dinic。“如果说网络流是图论中的‘交通调度’那么Dinic算法就是用‘分层立交桥’把混乱的交通梳理成高效流水线——车流量按层流动每条路只走一次绝不回头。”前置知识在阅读本文之前建议你熟悉以下概念流网络由源点、汇点、节点和有容量限制的有向边组成。残留网络与反向边允许“反悔”的机制是Ford-Fulkerson思想的核心。增广路在残留网络中从源点到汇点的一条路径沿路可以增加流量。BFS与DFSDinic算法的两大遍历工具。图的邻接表存储使用vector或链式前向星存储边。第一章从Ford-Fulkerson说起——为什么需要更好的算法1.1 Ford-Fulkerson的核心思想所有最大流算法的基石都是增广路的思想从零流开始。在残留网络中寻找一条从源点 ss 到汇点 tt 的路径增广路。沿着这条路增加尽可能多的流量等于路径上残留容量的最小值。更新残留网络正向边容量减少反向边容量增加。重复步骤2-4直到找不到增广路为止。这个思路简单而优雅但有一个致命的问题寻找增广路的方式决定了算法的效率。1.2 朴素FF的“灾难场景”如果随意找增广路比如用DFS在最坏情况下算法可能会反复增广一条很“蠢”的路导致时间复杂度与最大流量值 FF 相关即 O(E⋅F)O(E⋅F)。考虑一个流量为 109109 的网络如果每次只增广1单位流量算法将执行 109109 次DFS——这是不可接受的。1.3 Edmonds-Karp的改进Edmonds-Karp算法给出的改进是每次用BFS找最短增广路即边数最少的路径。这样做的效果是惊人的——算法复杂度降到了 O(VE2)O(VE2)彻底摆脱了对流量值的依赖。但 O(VE2)O(VE2) 在 V104,E105V104,E105 时仍然是天文数字。Dinic算法正是在这个基础上更进一步。第二章Dinic的核心思想——分层与阻塞流2.1 分层图Level GraphDinic算法的第一个核心创新是用BFS将所有节点按到源点的距离分层。源点 ss 在第0层。从 ss 出发一步能到达的节点在第1层。从第1层节点出发一步能到达的未分层节点在第2层。以此类推直到汇点 tt 被分层。分层之后我们只关注从第 ii 层指向第 i1i1 层的边——这些边构成了分层图。在分层图上任何从 ss 到 tt 的路径都一定是最短增广路边数最少。2.2 阻塞流Blocking FlowDinic算法的第二个核心思想是在一次BFS分层后通过DFS尽可能多地找到并增广所有从 ss 到 tt 的路径直到分层图中不再存在任何从 ss 到 tt 的路径。这个“最大”的流被称为阻塞流。为什么叫阻塞流因为增广完阻塞流后分层图中从 ss 到 tt 的所有路径都被“阻塞”了——每条路径上至少有一条边的容量变成了0。当阻塞流被计算完毕后我们再重新BFS分层重复这个过程直到BFS无法到达汇点 tt 为止。2.3 算法流程概览textDinic(s, t): 总流量 0 循环: BFS(s, t) 构建分层图 如果 t 不可达跳出循环 初始化当前弧指针 循环: flow DFS(s, t, INF) 如果 flow 0跳出循环 总流量 flow 返回 总流量2.4 为什么要多次BFS每次增广都会改变残留网络中边的容量这可能会导致某些节点之间的“层级关系”发生变化。因此在一次阻塞流计算完毕后需要重新BFS来获取新的分层图。但好消息是每次BFS后汇点 tt 的层级严格递增。因此BFS的次数最多为 VV 次这也是算法复杂度有保证的关键。第三章Dinic的关键优化——当前弧3.1 什么是当前弧在DFS寻找增广路时我们通常会遍历从当前节点出发的所有出边。但一个节点可能有很多出边而其中某些出边可能已经被“榨干”了容量变成0或者指向的节点在当前分层图中无法到达汇点。当前弧优化的核心思想是为每个节点记录一个指针cur[u]指向“下一条还有可能增广的边”。在DFS过程中一旦发现某条边不能再贡献流量容量为0或指向的节点无法到达汇点我们就将cur[u]向后移动下次再访问节点 uu 时直接从cur[u]开始跳过已经失效的边。3.2 当前弧优化的威力不使用当前弧优化时每次DFS从节点 uu 出发都要从第一条边开始遍历造成大量重复工作。使用了当前弧优化后每条边在同一轮BFS中最多被访问一次——要么它被用来运输了流量边容量归零要么它被证明是“死路”。这大大降低了DFS的复杂度是Dinic算法能跑得飞快的关键原因。3.3 一个小例子理解指针推进假设节点 uu 有出边 e1,e2,e3,e4e1,e2,e3,e4DFS第一次访问 uu尝试 e1e1发现 e1e1 的容量已满cap0于是cur[u]指向 e2e2。DFS第二次访问 uu直接从 e2e2 开始尝试发现 e2e2 通往的节点在分层图中无法到达汇点于是cur[u]指向 e3e3。这样e1e1 和 e2e2 永远不会被再次尝试节省了时间。第四章算法实现——Dinic的完整代码4.1 边结构的存储网络流算法需要处理反向边因此推荐使用邻接表 边编号的方式存储。每条边存储三个信息目标节点to、残留容量cap、反向边编号rev。cppstruct Edge { int to, rev; // 目标节点反向边在邻接表中的下标 int cap; // 残留容量int 或 long long }; vectorEdge g[MAXN];添加边时正向边和反向边成对添加cppvoid add_edge(int u, int v, int c) { g[u].push_back({v, (int)g[v].size(), c}); g[v].push_back({u, (int)g[u].size() - 1, 0}); }4.2 完整Dinic模板cpp#include bits/stdc.h using namespace std; const int MAXN 10005; const int INF 0x3f3f3f3f; struct Edge { int to, rev, cap; }; vectorEdge g[MAXN]; int level[MAXN]; // BFS分层深度 int it[MAXN]; // 当前弧指针it[u]表示从第几条边开始尝试 void add_edge(int u, int v, int c) { g[u].push_back({v, (int)g[v].size(), c}); g[v].push_back({u, (int)g[u].size() - 1, 0}); } // BFS构建分层图返回汇点是否可达 bool bfs(int s, int t) { memset(level, -1, sizeof(level)); queueint q; level[s] 0; q.push(s); while (!q.empty()) { int u q.front(); q.pop(); for (auto e : g[u]) { if (e.cap 0 level[e.to] 0) { level[e.to] level[u] 1; q.push(e.to); } } } return level[t] 0; } // DFS寻找增广路 int dfs(int u, int t, int f) { if (u t) return f; for (int i it[u]; i (int)g[u].size(); i) { // 当前弧优化 Edge e g[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; g[e.to][e.rev].cap d; return d; } } } return 0; } int max_flow(int s, int t) { int flow 0; while (bfs(s, t)) { memset(it, 0, sizeof(it)); while (true) { int f dfs(s, t, INF); if (f 0) break; flow f; } } return flow; }4.3 代码逐段解析BFS部分标准的广度优先搜索只走残留容量为正的边。level数组记录了每个节点的层数用于指导后续的DFS。DFS部分从节点 uu 开始向下一层的节点推进。关键点有三只走向level[v] level[u] 1的节点确保路径严格分层。使用引用int i it[u]这样当i递增时会同步修改it[u]。递归返回的流量d如果大于0则更新正向边和反向边的容量。主循环外层while(bfs)负责每次重新分层内层while(true)负责在当前分层图上反复DFS直到阻塞流形成。第五章经典例题精解——洛谷 P3376 【模板】网络最大流5.1 题目呈现题目来源洛谷 P3376 【模板】网络最大流题目描述如题给出一个网络图以及其源点和汇点求出其网络最大流。输入格式第一行四个整数 N,M,S,TN,M,S,T节点数、边数、源点编号、汇点编号接下来 MM 行每行三个整数 u,v,cu,v,c表示从 uu 到 vv 有一条容量为 cc 的边输出格式一行一个整数表示最大流输入样例text4 5 1 4 1 2 30 1 3 20 2 3 20 2 4 20 3 4 30输出样例text505.2 样例解析网络结构如下源点1有两条出边到2容量30和到3容量20节点2有两条出边到3容量20和到4容量20节点3有一条出边到4容量30最大流路径路径11 → 2 → 4流量20受限于1→2的剩余容量和2→4的容量路径21 → 2 → 3 → 4流量101→2剩余102→3容量203→4容量30路径31 → 3 → 4流量201→3容量203→4剩余20总流量 20 10 20 505.3 完整AC代码cpp#include bits/stdc.h using namespace std; typedef long long ll; const int MAXN 205; // N 200小规模 const ll INF 1e18; struct Edge { int to, rev; ll cap; }; vectorEdge g[MAXN]; int level[MAXN], it[MAXN]; int N, M, S, T; void add_edge(int u, int v, ll c) { g[u].push_back({v, (int)g[v].size(), c}); g[v].push_back({u, (int)g[u].size() - 1, 0}); } bool bfs() { memset(level, -1, sizeof(level)); queueint q; level[S] 0; q.push(S); while (!q.empty()) { int u q.front(); q.pop(); for (auto e : g[u]) { if (e.cap 0 level[e.to] 0) { level[e.to] level[u] 1; q.push(e.to); } } } return level[T] 0; } ll dfs(int u, ll f) { if (u T) return f; for (int i it[u]; i (int)g[u].size(); i) { Edge e g[u][i]; if (e.cap 0 level[e.to] level[u] 1) { ll d dfs(e.to, min(f, e.cap)); if (d 0) { e.cap - d; g[e.to][e.rev].cap d; return d; } } } return 0; } ll max_flow() { ll flow 0; while (bfs()) { memset(it, 0, sizeof(it)); while (true) { ll f dfs(S, INF); if (f 0) break; flow f; } } return flow; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin N M S T; for (int i 0; i M; i) { int u, v; ll c; cin u v c; add_edge(u, v, c); } cout max_flow() \n; return 0; }5.4 复杂度分析时间复杂度O(V2E)O(V2E)。其中 VV 为节点数EE 为边数。对于本题 N≤200N≤200几乎没有压力。空间复杂度O(VE)O(VE)因为每条边存储两次正向反向。5.5 关于INF的取值如果边的容量最大为 109109NN 最大为 104104那么最大流可能达到 10131013 级别。此时需要用long long并设置INF 4e18。如果容量较小如 104104用int即可INF 0x3f3f3f3f。第六章Dinic与其他算法的对比6.1 算法对比一览算法时间复杂度适用场景优点缺点Ford-FulkersonO(E⋅F)O(E⋅F)流量值较小思想简单易于理解依赖流量值可能极慢Edmonds-KarpO(VE2)O(VE2)通用复杂度与流量值无关稠密图表现不佳DinicO(V2E)O(V2E)通用竞赛首选实际运行飞快当前弧优化强实现略复杂ISAPO(V2E)O(V2E)通用比Dinic在某些场景更快实现更复杂6.2 为什么Dinic“实际跑得飞快”尽管Dinic的理论复杂度是 O(V2E)O(V2E)但在实际应用中它通常表现得远比这个上界好。原因有BFS次数少在实际网络流中BFS分层的次数通常远小于 VV。当前弧优化极大地减少了DFS中的重复遍历。边容量饱和快在DFS过程中一旦某条边被完全使用容量归零它在当前轮次中就不会再被考虑。6.3 什么时候用Dinic什么时候用其他通用场景无脑用Dinic。它是算法竞赛中最安全、最广泛使用的网络流算法。二分图匹配Dinic可以跑 O(EV)O(EV)但匈牙利算法实现更简单对于小规模数据更推荐。费用流Dinic处理的是最大流最小费用最大流需要用SPFA/Dijkstra Dinic的变种即MCMF。边数极多、节点极少Edmonds-Karp可能更简单。需要更优理论界ISAPImproved Shortest Augmenting Path在某些情况下比Dinic更快。总结网络流是图论中一个极其丰富的分支而Dinic算法则是这个分支中最锋利的利刃。它用分层图切断了“胡乱找路”的混乱用当前弧优化抹去了“重复尝试”的低效将最大流问题带入了 O(V2E)O(V2E) 的高效时代。无论你是算法竞赛选手还是面试准备者Dinic都是必学的核心算法之一。三个关键点分层图是骨架每次BFS将网络分层DFS只沿分层方向推进保证每次增广的都是最短路径。当前弧是灵魂it[u]指针让每条边在同一轮次中只被尝试一次大幅降低复杂度。阻塞流是目标每轮BFS后DFS不断增广直到形成阻塞流然后重新分层。“Dinic算法教会我们效率不是靠蛮力堆砌出来的而是靠合理的分层调度和精准的路径选择达成的——在复杂的网络中告诉每一条流‘该往哪走’比让它们‘乱冲乱撞’要高效得多。”参考文献与延伸阅读《算法导论》第26章——最大流OI-Wiki网络流 - 最大流洛谷 P3376 【模板】网络最大流洛谷 P2756 飞行员配对方案问题二分图匹配Dinic应用《挑战程序设计竞赛》第7章——最大流Yosupo Judge - Maximum Flow性能测试题