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

匹配题怎么转成最大流

匹配题怎么转成最大流

当题目要求“把人分给岗位”“把任务分给机器”并且每个对象都有可选关系与容量上限时,二分图匹配往往可以直接改写成最大流。关键不是记模板,而是把“谁能选谁”和“每边能用几次”翻译成边与容量。

学习目标

  • 识别可以转成二分图匹配的分配问题
  • 构造源点、左右两侧节点、汇点与容量
  • 用最大流结果还原匹配数量,并扩展到多容量场景

从“配对”识别二分图

如果对象天然分成两类,合法关系只发生在两类之间,就可以先按二分图理解。例如候选人只能选择岗位,候选人之间、岗位之间都没有直接配对关系。

标准一对一匹配还隐含两个容量条件:每个左侧对象最多被使用一次,每个右侧对象最多接收一次。最大匹配要找的就是最多能同时成立多少条互不冲突的左右边。

四层网络怎么搭

把二分图变成流网络时,使用“源点 → 左侧 → 右侧 → 汇点”四层结构。源点到每个左侧节点容量设为 1;允许配对的左右节点之间连容量为 1 的边;每个右侧节点到汇点容量设为 1。

二分图匹配转最大流的四层结构

这样建模后,每条从源点走到汇点的单位流都会消耗一个左侧名额、一个合法关系和一个右侧名额。由于容量都是整数,最大流可以得到整数流,因此中间取到流量 1 的左右边正好对应被选中的匹配。

跑一个完整例子

下面用 Edmonds-Karp 求三名候选人与三个岗位的最大匹配。A 可去 X、Y,B 可去 Y,C 可去 Y、Z。

python
from collections import deque

def max_flow(capacity, source, sink):
    n = len(capacity)
    residual = [row[:] for row in capacity]
    total = 0

    while True:
        parent = [-1] * n
        parent[source] = source
        q = deque([source])

        while q and parent[sink] == -1:
            u = q.popleft()
            for v, cap in enumerate(residual[u]):
                if cap > 0 and parent[v] == -1:
                    parent[v] = u
                    q.append(v)

        if parent[sink] == -1:
            return total

        # 本例所有有效边容量为 1,因此每次增广一条匹配路径。
        flow = 10**9
        v = sink
        while v != source:
            u = parent[v]
            flow = min(flow, residual[u][v])
            v = u

        v = sink
        while v != source:
            u = parent[v]
            residual[u][v] -= flow
            residual[v][u] += flow
            v = u

        total += flow

names = ["S", "A", "B", "C", "X", "Y", "Z", "T"]
idx = {name: i for i, name in enumerate(names)}
capacity = [[0] * len(names) for _ in names]

for person in ["A", "B", "C"]:
    capacity[idx["S"]][idx[person]] = 1

for job in ["X", "Y", "Z"]:
    capacity[idx[job]][idx["T"]] = 1

for person, job in [("A", "X"), ("A", "Y"), ("B", "Y"), ("C", "Y"), ("C", "Z")]:
    capacity[idx[person]][idx[job]] = 1

print("最大匹配数:", max_flow(capacity, idx["S"], idx["T"]))

预期输出

text
最大匹配数: 3

这里得到 3,说明三名候选人都能被分配到互不冲突的岗位,例如 A→X、B→Y、C→Z。具体是哪一组匹配取决于增广路径顺序,但最大匹配数量不变。

容量限制怎么扩展

如果岗位 Y 可以招 3 人,只需把 Y→T 的容量从 1 改成 3;如果某个左侧对象可以承担 2 个任务,则把 S→该节点 的容量改成 2。允许关系边的容量通常仍为 1,表示同一对关系不能重复使用。

这就是网络流比“只记二分图匹配模板”更通用的地方:一对一是容量全为 1 的特例,多岗位名额、机器并发槽位、课程选课上限都可以通过改容量表达。

建模时最容易错的地方

先确认左右两类是否真的彼此独立,再确认每个对象的“最多几次”应该落在哪条边上。不要把“可以选择”误写成“必须选择”,也不要把源点或汇点容量设得过小,否则会人为限制答案。

如果关系之外还出现成本、优先级或收益,单纯最大流只能回答“最多能分配多少”。这时通常要进一步使用最小费用最大流等模型,而不是继续往容量里硬塞权重。

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

目录与阅读设置

阅读设置

17

记录一个想法

匹配题怎么转成最大流

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

登录哪都通