数据结构与算法 / 系统课时

什么题可以建成网络流

什么题可以建成网络流

很多“把有限资源分给若干对象”的题,真正难点不是跑最大流,而是判断约束能否被容量和流量守恒表达。本节给出一套识别方法,并用最小可运行程序验证建模是否正确。

学习目标

  • 从题意中识别源点、汇点、容量和中间决策节点
  • 把“最多使用几次”“必须经过某层”等限制翻译成边容量或拆点
  • 用最大流结果检查建模是否符合原问题

先看约束是否像“流”

适合网络流的题通常同时出现四类信息:有东西从若干来源出发、有明确去向、中间经过若干选择关系、每条关系或资源存在上限。此时可以把“东西”抽象成单位流量,把限制抽象成容量。

常见信号包括:

  • “最多分配多少”“最多完成多少”通常对应最大流目标。
  • “某资源最多使用 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。

python
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"))

预期输出

text
max_flow = 5

结果为 5,说明从源点最多能送出并最终到达汇点 5 单位流量。实际题目中,最大流的数值应能直接解释成“最多完成的分配数”“最多通过的单位数”或其他明确业务量。

什么时候不要硬套网络流

如果题目只是在求最短距离、连通性或单纯的拓扑顺序,没有“容量上限 + 从源到汇的分配”这类结构,网络流通常不是最短路径。另一个警告信号是约束依赖全局组合关系,例如“选了 A 就必须同时选 B 或 C 中恰好一个”,这类约束未必能仅靠普通容量边表达。

判断是否值得建流网络的核心不是“看起来像图”,而是原问题能否稳定地翻译成流量、容量与守恒三个要素。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

什么题可以建成网络流

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通