数据结构与算法 / 系统课时
最小割和最大流怎么对应
最小割和最大流怎么对应
最大流给出“最多能送多少”,最小割解释“为什么再也送不动”。把最大流结束后的残量网络从源点做一次可达性搜索,就能得到一个最小割,并把限制总吞吐量的那组容量边直接找出来。
学习目标
- 理解割、割容量与任意可行流之间的上界关系。
- 能从最大流的最终残量网络中恢复一个最小割。
- 能用割边解释瓶颈,同时避免把单条割边过度解读为唯一根因。
割为什么天然限制最大流
对源点 s 和汇点 t,把全部顶点分成两组:S 包含 s,T 包含 t。所有从 S 指向 T 的原图边构成这个割的正向跨割边,它们的容量总和就是割容量。
任何从 s 送到 t 的流都必须跨过这条边界,所以任意可行流的流量都不会超过任意一个割的容量。换句话说,所有割都在给最大流提供上界,而最小割给出其中最紧的那个上界。

关键点在于:最小割不是靠枚举所有分组找到的。最大流算法结束时,残量网络已经把这个分组“留下来了”。
为什么最终残量图能给出最小割
最大流结束意味着残量网络中不存在从 s 到 t 的路径。此时从 s 出发,只沿剩余容量大于 0 的边搜索,把所有可达点记为 S,不可达点记为 T。
由于 t 不可达,二者确实形成合法的源汇割。更重要的是,任何从 S 指向 T 的原图边都必须已经饱和,否则还有正残量可以跨过去;而任何从 T 指回 S 且承载正向流量的原图边,都会在残量网络产生一条从 S 到 T 的反向残量边,同样与不可达性矛盾。
因此,这个割上的净流量正好等于跨割容量,也等于当前最大流值。于是得到最大流最小割定理:最大流值等于最小割容量。
用程序恢复一个最小割
下面的完整示例先用 Dinic 求最大流,再在最终残量网络里搜索 s 的可达点。为了方便解释结果,同时保留原始边列表,并据此列出从 S 跨到 T 的割边。
from collections import deque
from dataclasses import dataclass
@dataclass
class Edge:
to: int
rev: int
cap: int
class Dinic:
def __init__(self, n: int):
self.g = [[] for _ in range(n)]
self.level = [-1] * n
self.ptr = [0] * n
self.original_edges = []
def add_edge(self, u: int, v: int, cap: int) -> None:
fwd = Edge(v, len(self.g[v]), cap)
rev = Edge(u, len(self.g[u]), 0)
self.g[u].append(fwd)
self.g[v].append(rev)
self.original_edges.append((u, v, cap))
def bfs(self, s: int, t: int) -> bool:
self.level = [-1] * len(self.g)
self.level[s] = 0
q = deque([s])
while q:
u = q.popleft()
for e in self.g[u]:
if e.cap > 0 and self.level[e.to] == -1:
self.level[e.to] = self.level[u] + 1
q.append(e.to)
return self.level[t] != -1
def dfs(self, u: int, t: int, pushed: int) -> int:
if u == t or pushed == 0:
return pushed
while self.ptr[u] < len(self.g[u]):
e = self.g[u][self.ptr[u]]
if e.cap > 0 and self.level[e.to] == self.level[u] + 1:
flow = self.dfs(e.to, t, min(pushed, e.cap))
if flow > 0:
e.cap -= flow
self.g[e.to][e.rev].cap += flow
return flow
self.ptr[u] += 1
return 0
def max_flow(self, s: int, t: int) -> int:
# 先求最大流;最终残量网络会被 min_cut 继续使用。
total = 0
while self.bfs(s, t):
self.ptr = [0] * len(self.g)
while True:
pushed = self.dfs(s, t, 10**18)
if pushed == 0:
break
total += pushed
return total
def min_cut(self, s: int):
# 最大流完成后,只沿正残量边找从 s 仍然可达的节点。
reachable = [False] * len(self.g)
q = deque([s])
reachable[s] = True
while q:
u = q.popleft()
for e in self.g[u]:
if e.cap > 0 and not reachable[e.to]:
reachable[e.to] = True
q.append(e.to)
s_side = [v for v, ok in enumerate(reachable) if ok]
t_side = [v for v, ok in enumerate(reachable) if not ok]
cut_edges = [
(u, v, c)
for u, v, c in self.original_edges
if reachable[u] and not reachable[v]
]
return s_side, t_side, cut_edges
if __name__ == "__main__":
dinic = Dinic(4)
for u, v, c in [
(0, 1, 4),
(0, 2, 2),
(1, 2, 1),
(1, 3, 2),
(2, 3, 3),
]:
dinic.add_edge(u, v, c)
flow = dinic.max_flow(0, 3)
s_side, t_side, cut_edges = dinic.min_cut(0)
print("max_flow =", flow)
print("S_side =", s_side)
print("T_side =", t_side)
print("cut_edges =", cut_edges)
print("cut_capacity =", sum(c for _, _, c in cut_edges))预期输出
max_flow = 5
S_side = [0, 1]
T_side = [2, 3]
cut_edges = [(0, 2, 2), (1, 2, 1), (1, 3, 2)]
cut_capacity = 5这里的割容量 2 + 1 + 2 = 5,恰好等于最大流值 5。节点 0 和 1 在最终残量网络中仍可从源点到达,但无法再跨过三条已经饱和的割边进入 T 区域。
怎样用最小割解释建模结果
在“容量受限的分配”模型中,最小割给出的不是抽象证明而是瓶颈边界。例如把边理解为机房带宽、仓库出货能力或任务配额,割边集合表示当前所有源汇路径共同绕不过去的容量约束。
但不要把“属于某个最小割”直接理解成“只要扩这一条边,最大流一定增加”。最小割可能不唯一;即使提高一条割边容量,另一组同容量的最小割仍可能继续限制总流量。更可靠的做法是修改容量后重新求最大流和最小割,再观察瓶颈是否迁移。
最容易混淆的两个边界
第一,割容量只统计原图中从 S 指向 T 的边容量,不是把所有跨分区的双向容量都相加。第二,最小割描述的是一组容量约束的整体瓶颈,不等同于单条“最差边”。
当最大流值和最小割容量一致时,你既得到了最优数值,也得到了一个可验证的最优性证据:任何方案都无法超过这个割的容量上界,而当前流已经达到它。