我最早学网络流时，觉得 Edmonds-Karp 就够用了：BFS 找增广路，逻辑简单，代码也短。直到我拿它去跑一个上千节点、万级边的二分图匹配，发现每次迭代只能榨出一条路，慢得让人怀疑人生。后来换用 Dinic，代码量其实没增加太多，速度却有了质的飞跃。
Dinic 的核心就做了两件事：分层图 和 阻塞流。用 BFS 给残量网络分层，再在分层有向无环图上用 DFS 一次性抽出所有能找到的增广路——这样一轮下来就清空了当前层级的可行流，远胜每次只找一条路的打法。加上一个不起眼的 当前弧优化，能让 DFS 跳过已经饱和的边，避免重复试探。
下面是我常用的一个实现，带完整的最小割计算。
from collections import deque
class Dinic:
def __init__(self, n, source, sink):
self.n = n
self.source = source
self.sink = sink
# 邻接表：每条边存 (目标, 剩余容量, 反向边索引)
self.graph = [[] for _ in range(n)]
self.level = [-1] * n
self.ptr = [0] * n
def add_edge(self, u, v, capacity):
forward = (v, capacity, len(self.graph[v]))
backward = (u, 0, len(self.graph[u]))
self.graph[u].append(forward)
self.graph[v].append(backward)
def bfs_level(self):
self.level = [-1] * self.n
q = deque()
self.level[self.source] = 0
q.append(self.source)
while q:
u = q.popleft()
for v, cap, _ in self.graph[u]:
if self.level[v] == -1 and cap > 0:
self.level[v] = self.level[u] + 1
q.append(v)
if v == self.sink:
return True
return self.level[self.sink] != -1
def dfs_flow(self, u, flow_limit):
if u == self.sink:
return flow_limit
while self.ptr[u] < len(self.graph[u]):
edge_idx = self.ptr[u]
v, cap, rev_idx = self.graph[u][edge_idx]
if self.level[v] == self.level[u] + 1 and cap > 0:
min_flow = min(flow_limit, cap)
aug_flow = self.dfs_flow(v, min_flow)
if aug_flow > 0:
# 更新正向边
self.graph[u][edge_idx] = (v, cap - aug_flow, rev_idx)
# 更新反向边
rev_v, rev_cap, rev_rev_idx = self.graph[v][rev_idx]
self.graph[v][rev_idx] = (rev_v, rev_cap + aug_flow, rev_rev_idx)
return aug_flow
self.ptr[u] += 1
return 0
def max_flow(self):
total_flow = 0
while self.bfs_level():
self.ptr = [0] * self.n
while True:
flow = self.dfs_flow(self.source, float('inf'))
if flow == 0:
break
total_flow += flow
return total_flow
def min_cut(self):
""" 调用 max_flow 后，可从残量网络计算最小割 """
visited = [False] * self.n
q = deque()
q.append(self.source)
visited[self.source] = True
while q:
u = q.popleft()
for v, cap, _ in self.graph[u]:
if not visited[v] and cap > 0:
visited[v] = True
q.append(v)
S = [i for i in range(self.n) if visited[i]]
T = [i for i in range(self.n) if not visited[i]]
# 计算割容量：所有从 S 连出的原边容量之和
cut_capacity = 0
for u in S:
for v, cap, rev_idx in self.graph[u]:
if v in T:
rev_cap = self.graph[v][rev_idx][1]
cut_capacity += cap + rev_cap
return S, T, cut_capacity
# 简单测试
if __name__ == "__main__":
n = 4
dinic = Dinic(n, 0, 3)
dinic.add_edge(0, 1, 3)
dinic.add_edge(0, 2, 2)
dinic.add_edge(1, 2, 1)
dinic.add_edge(1, 3, 2)
dinic.add_edge(2, 3, 3)
print("最大流值：", dinic.max_flow()) # 输出 5
S, T, cut = dinic.min_cut()
print(f"最小割 S 集合：{S}")
print(f"最小割 T 集合：{T}")
print(f"最小割容量：{cut}") # 输出 5
这个实现里，bfs_level 每次重新构建分层图，汇点在 BFS 过程中一旦被标记就提前返回——这一点点优化在汇点离源点很近时能省不少时间。dfs_flow 用 ptr 数组记住每个节点已检查到哪条边，这样已饱和的边不会在后续递归中重复访问。注意每次 bfs_level 之后务必把 ptr 清零，否则会错过很多可行边。
为什么分层图这么重要？
在没有分层的情况下，DFS 可能钻进一条很深的死路，或者绕圈子。分层图保证了每次走一步，层次严格递增，图自然变成了 DAG，DFS 不会形成环。同时，分层本身就是一种'最短路'保证：你每次推的流量走的都是残量意义上最短的路，算法收敛很快。
当前弧优化，小技巧大作用
如果没有 ptr，DFS 每次调用都会从头扫描邻接表，对于扇出大的节点，这在分层图被反复使用时会做大量无用功。当前弧优化把每个节点的内层循环状态保留下来，饱和边跳过，等价于把多次遍历平摊下来。这个优化能将 Dinic 的理论上限从 O(V²E) 的宽松界拉到实践中几乎线性。
性能对比
Edmonds-Karp 每轮 O(V+E) 的 BFS 只找到一条增广路，增广次数可能多达 O(VE)。Dinic 的每一轮分层+阻塞流远不止一条路，迭代轮数通常在 O(V) 以内。在手写的测试里，小图差别不大，但顶点上了 500 以后，Dinic 的优势就非常明显。
对于二分图最大匹配，Dinic 更是能跑到 O(E√V)，因为分层深度最多 O(√V)。这也是为什么竞赛题里你很少看到 EK 的影子。
最小割怎么取？
最大流等于最小割容量，这早就是定理了。代码里 min_cut 做的事情就是跑完最大流后，直接在残量网络上从源点 BFS，能到达的节点属于 S，其余属于 T。割的容量等于从 S 连向 T 的原边容量之和——注意这里的原边容量是正向残量加反向残量，因为残量网络已经消耗了部分容量。
写这类代码时的几个坑
- 反向边索引：添加边时，正向边要存下反向边在目标点邻接表中的位置，反向边也一样。一旦索引搞错，残量更新就会写到错误的位置，最大流当然也会算错。
- 重置 ptr 的时机：每重新分层后必须重置，否则 ptr 中残留的旧索引会让你错过有效的出边。我就在这上面浪费过不少调试时间。
- 无向边：如果需要无向边，拆成两条方向相反、容量相同的有向边就行，但别忘了它们的反向边需要互相对应。
- large scale：Python 实现可能受限于递归深度（
dfs_flow是递归的）。如果图深度很大，建议手动维护栈，或者直接用迭代版。
Dinic 在工程上很平衡：比 EK 快得多，又不像 Push-Relabel 那样概念复杂。如果你的场景经常要处理几千个节点的网络流，这个实现能省下大量时间。
