Dinic算法：网络最大流的“高效流水线”

如果说Ford-Fulkerson是“一条一条地找路，找到一条就走一条”的勤劳搬运工，那么Dinic算法就是“一次规划好所有路线，然后分阶段批量运输”的物流调度专家——它用分层图和当前弧优化，将网络流的效率提升到了理论最优的极致。

引言

你有两个工厂和一个仓库，中间是一张错综复杂的管道网络，每个管道每秒钟有固定的最大输送量。问题是：从工厂到仓库，每秒钟最多能输送多少货物？

这个问题听起来简单，但管道网络可能包含成千上万个节点和边，你不可能手动去一条条试。网络流算法就是为解决这类“最大输送能力”问题而生的。

最朴素的Ford-Fulkerson算法虽然思想直观——不断找增广路并增加流量——但它的时间复杂度取决于流量值，在流量很大的情况下会慢到无法接受。Edmonds-Karp算法通过BFS找增广路将复杂度优化到了 O(VE2)O(VE2)，但当 VV 和 EE 都达到 104104 级别时，仍然捉襟见肘。

Dinic算法是网络流算法家族中最耀眼的一颗明星。它在Edmonds-Karp的基础上引入了“分层图”和“当前弧优化”两大杀手锏，将时间复杂度优化到了 O(V2E)O(V2E)，并且在绝大多数实际场景中表现得远比这个上界要好。如果你只能掌握一种网络流算法，那一定是Dinic。

“如果说网络流是图论中的‘交通调度’，那么Dinic算法就是用‘分层立交桥’把混乱的交通梳理成高效流水线——车（流量）按层流动，每条路只走一次，绝不回头。”

前置知识

在阅读本文之前，建议你熟悉以下概念：

1. 流网络：由源点、汇点、节点和有容量限制的有向边组成。

2. 残留网络与反向边：允许“反悔”的机制，是Ford-Fulkerson思想的核心。

3. 增广路：在残留网络中从源点到汇点的一条路径，沿路可以增加流量。

4. BFS与DFS：Dinic算法的两大遍历工具。

5. 图的邻接表存储：使用vector或链式前向星存储边。

第一章：从Ford-Fulkerson说起——为什么需要更好的算法

1.1 Ford-Fulkerson的核心思想

所有最大流算法的基石都是增广路的思想：

1. 从零流开始。

2. 在残留网络中寻找一条从源点 ss 到汇点 tt 的路径（增广路）。

3. 沿着这条路增加尽可能多的流量（等于路径上残留容量的最小值）。

4. 更新残留网络（正向边容量减少，反向边容量增加）。

5. 重复步骤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) 在 V=104,E=105V=104,E=105 时仍然是天文数字。Dinic算法正是在这个基础上更进一步。

第二章：Dinic的核心思想——分层与阻塞流

2.1 分层图（Level Graph）

Dinic算法的第一个核心创新是：用BFS将所有节点按到源点的距离分层。

• 源点 ss 在第0层。

• 从 ss 出发，一步能到达的节点在第1层。

• 从第1层节点出发，一步能到达的未分层节点在第2层。

• 以此类推，直到汇点 tt 被分层。

分层之后，我们只关注从第 ii 层指向第 i+1i+1 层的边——这些边构成了分层图。在分层图上，任何从 ss 到 tt 的路径都一定是最短增广路（边数最少）。

2.2 阻塞流（Blocking Flow）

Dinic算法的第二个核心思想是：在一次BFS分层后，通过DFS尽可能多地找到并增广所有从 ss 到 tt 的路径，直到分层图中不再存在任何从 ss 到 tt 的路径。这个“最大”的流被称为阻塞流。

为什么叫阻塞流？因为增广完阻塞流后，分层图中从 ss 到 tt 的所有路径都被“阻塞”了——每条路径上至少有一条边的容量变成了0。

当阻塞流被计算完毕后，我们再重新BFS分层，重复这个过程，直到BFS无法到达汇点 tt 为止。

2.3 算法流程概览

text

Dinic(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​,e4​：

• DFS第一次访问 uu，尝试 e1e1​，发现 e1e1​ 的容量已满（cap=0），于是cur[u]指向 e2e2​。

• DFS第二次访问 uu，直接从 e2e2​ 开始尝试，发现 e2e2​ 通往的节点在分层图中无法到达汇点，于是cur[u]指向 e3e3​。

• 这样，e1e1​ 和 e2e2​ 永远不会被再次尝试，节省了时间。

第四章：算法实现——Dinic的完整代码

4.1 边结构的存储

网络流算法需要处理反向边，因此推荐使用邻接表 + 边编号的方式存储。每条边存储三个信息：目标节点to、残留容量cap、反向边编号rev。

cpp

struct Edge { int to, rev; // 目标节点，反向边在邻接表中的下标 int cap; // 残留容量（int 或 long long） }; vector<Edge> g[MAXN];

添加边时，正向边和反向边成对添加：

cpp

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}); }

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; }; vector<Edge> 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)); queue<int> 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 的边

输出格式：

• 一行，一个整数，表示最大流

输入样例：

text

4 5 1 4 1 2 30 1 3 20 2 3 20 2 4 20 3 4 30

输出样例：

text

50

5.2 样例解析

网络结构如下：

• 源点1有两条出边：到2（容量30）和到3（容量20）

• 节点2有两条出边：到3（容量20）和到4（容量20）

• 节点3有一条出边：到4（容量30）

最大流路径：

• 路径1：1 → 2 → 4，流量20（受限于1→2的剩余容量和2→4的容量）

• 路径2：1 → 2 → 3 → 4，流量10（1→2剩余10，2→3容量20，3→4容量30）

• 路径3：1 → 3 → 4，流量20（1→3容量20，3→4剩余20）

总流量 = 20 + 10 + 20 = 50

5.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; }; vector<Edge> 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)); queue<int> 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(V+E)O(V+E)，因为每条边存储两次（正向+反向）。

5.5 关于INF的取值

如果边的容量最大为 109109，NN 最大为 104104，那么最大流可能达到 10131013 级别。此时需要用long long并设置INF = 4e18。

如果容量较小（如 104104），用int即可，INF = 0x3f3f3f3f。

第六章：Dinic与其他算法的对比

6.1 算法对比一览

6.2 为什么Dinic“实际跑得飞快”？

尽管Dinic的理论复杂度是 O(V2E)O(V2E)，但在实际应用中，它通常表现得远比这个上界好。原因有：

1. BFS次数少：在实际网络流中，BFS分层的次数通常远小于 VV。

2. 当前弧优化：极大地减少了DFS中的重复遍历。

3. 边容量饱和快：在DFS过程中，一旦某条边被完全使用（容量归零），它在当前轮次中就不会再被考虑。

6.3 什么时候用Dinic，什么时候用其他？

• 通用场景：无脑用Dinic。它是算法竞赛中最安全、最广泛使用的网络流算法。

• 二分图匹配：Dinic可以跑 O(EV)O(EV​)，但匈牙利算法实现更简单，对于小规模数据更推荐。

• 费用流：Dinic处理的是最大流，最小费用最大流需要用SPFA/Dijkstra + Dinic的变种（即MCMF）。

• 边数极多、节点极少：Edmonds-Karp可能更简单。

• 需要更优理论界：ISAP（Improved Shortest Augmenting Path）在某些情况下比Dinic更快。

总结

网络流是图论中一个极其丰富的分支，而Dinic算法则是这个分支中最锋利的利刃。它用分层图切断了“胡乱找路”的混乱，用当前弧优化抹去了“重复尝试”的低效，将最大流问题带入了 O(V2E)O(V2E) 的高效时代。无论你是算法竞赛选手还是面试准备者，Dinic都是必学的核心算法之一。

三个关键点：

1. 分层图是骨架：每次BFS将网络分层，DFS只沿分层方向推进，保证每次增广的都是最短路径。

2. 当前弧是灵魂：it[u]指针让每条边在同一轮次中只被尝试一次，大幅降低复杂度。

3. 阻塞流是目标：每轮BFS后，DFS不断增广直到形成阻塞流，然后重新分层。

“Dinic算法教会我们：效率不是靠蛮力堆砌出来的，而是靠合理的分层调度和精准的路径选择达成的——在复杂的网络中，告诉每一条流‘该往哪走’，比让它们‘乱冲乱撞’要高效得多。”

参考文献与延伸阅读

1. 《算法导论》第26章——最大流

2. OI-Wiki：网络流 - 最大流

3. 洛谷 P3376 【模板】网络最大流

4. 洛谷 P2756 飞行员配对方案问题（二分图匹配，Dinic应用）

5. 《挑战程序设计竞赛》第7章——最大流

6. Yosupo Judge - Maximum Flow（性能测试题）