数据结构与算法 / 系统课时
什么题可以建成网络流
什么题可以建成网络流
很多“把有限资源分给若干对象”的题,真正难点不是跑最大流,而是判断约束能否被容量和流量守恒表达。本节给出一套识别方法,并用最小可运行程序验证建模是否正确。
学习目标
- 从题意中识别源点、汇点、容量和中间决策节点
- 把“最多使用几次”“必须经过某层”等限制翻译成边容量或拆点
- 用最大流结果检查建模是否符合原问题
先看约束是否像“流”
适合网络流的题通常同时出现四类信息:有东西从若干来源出发、有明确去向、中间经过若干选择关系、每条关系或资源存在上限。此时可以把“东西”抽象成单位流量,把限制抽象成容量。
常见信号包括:
- “最多分配多少”“最多完成多少”通常对应最大流目标。
- “某资源最多使用 k 次”通常对应容量为 k 的边。
- “一个人只能选一个任务”“一个位置只能被占一次”常用容量 1 表达。
- 流量进入中间节点后必须继续流出,对应中间节点的流量守恒。

把题意翻译成节点和容量
建模时先问“谁提供流量,谁接收流量”。通常新建超级源点 S 连接所有供给者,新建超级汇点 T 接收所有合法结果。中间节点只表示决策阶段,不要把题目中的每个名词机械地变成节点。
如果限制落在“边”上,直接设容量即可。例如任务 A 最多接收 2 人,就让任务 A 到 T 的容量为 2。如果限制落在“节点”上,例如某个中转节点总共只能通过 1 单位流量,可把节点拆成 v_in 与 v_out,中间连一条容量为 1 的边,所有入边接 v_in,所有出边从 v_out 发出。
用一个最小程序验证建模
下面把两个供给节点 A、B 连接到汇点 T。S -> A 最多提供 3 单位,S -> B 最多提供 2 单位;中间允许 A 向 B 转移 1 单位。最大流应为 5。
from collections import defaultdict, deque
def max_flow(edges, source, sink):
capacity = defaultdict(int)
graph = defaultdict(list)
for u, v, c in edges:
capacity[(u, v)] += c
graph[u].append(v)
graph[v].append(u)
total = 0
while True:
parent = {source: None}
queue = deque([source])
# 在残量网络中寻找一条仍有容量的增广路
while queue and sink not in parent:
u = queue.popleft()
for v in graph[u]:
if v not in parent and capacity[(u, v)] > 0:
parent[v] = u
queue.append(v)
if sink not in parent:
break
bottleneck = float("inf")
v = sink
while v != source:
u = parent[v]
bottleneck = min(bottleneck, capacity[(u, v)])
v = u
# 扣减正向残量,同时增加反向残量
v = sink
while v != source:
u = parent[v]
capacity[(u, v)] -= bottleneck
capacity[(v, u)] += bottleneck
v = u
total += bottleneck
return total
edges = [
("S", "A", 3),
("S", "B", 2),
("A", "B", 1),
("A", "T", 2),
("B", "T", 3),
]
print("max_flow =", max_flow(edges, "S", "T"))预期输出
max_flow = 5结果为 5,说明从源点最多能送出并最终到达汇点 5 单位流量。实际题目中,最大流的数值应能直接解释成“最多完成的分配数”“最多通过的单位数”或其他明确业务量。
什么时候不要硬套网络流
如果题目只是在求最短距离、连通性或单纯的拓扑顺序,没有“容量上限 + 从源到汇的分配”这类结构,网络流通常不是最短路径。另一个警告信号是约束依赖全局组合关系,例如“选了 A 就必须同时选 B 或 C 中恰好一个”,这类约束未必能仅靠普通容量边表达。
判断是否值得建流网络的核心不是“看起来像图”,而是原问题能否稳定地翻译成流量、容量与守恒三个要素。