⚠️ 用最大流再算一遍匹配数

👁️ 0 人浏览 💬 0 人评论 ❤️ 添加收藏

五个人、四台机器。每个人只会开其中几台，一台机器同时只能一个人用，一个人也只能占一台：把匹配改写成一张管道网：总源 S 到每个人容量 1，人到他会开的机器容量 1，机器到总汇 T 容量 1。两种算法各算一次，输出两个数对账。

PEOPLE = ['阿岚', '小满', '阿泰', '南风', '北辰']
LIKE = {'阿岚': ['甲', '乙'], '小满': ['甲'], '阿泰': ['丙', '丁'],
        '南风': ['丙'],       '北辰': ['乙', '丁']}

提交你的答案

请登录后提交答案。

去登录

← 自己写：让前面的人挪个位 🔴 只把两个人对调，贪心就"对"了 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

PEOPLE = ['阿岚', '小满', '阿泰', '南风', '北辰']
LIKE = {'阿岚': ['甲', '乙'], '小满': ['甲'], '阿泰': ['丙', '丁'],
        '南风': ['丙'],       '北辰': ['乙', '丁']}

def hungarian(people, like):
    m = {}

def aug(p, seen):
        for t in like[p]:
            if t in seen:
                continue
            seen.add(t)
            if t not in m or aug(m[t], seen):
                m[t] = p
                return True
        return False

n = 0
    for p in people:
        if aug(p, set()):
            n += 1
    return n

from collections import deque

def maxflow(cap_in, s, t):
    cap = {a: dict(b) for a, b in cap_in.items()}
    for u in list(cap):
        for v in list(cap[u]):
            cap.setdefault(v, {}).setdefault(u, 0)
    flow = 0
    for _ in range(50):
        par = {s: None}
        q = deque([s])
        while q:
            u = q.popleft()
            for v, c in cap[u].items():
                if c > 0 and v not in par:
                    par[v] = u
                    q.append(v)
        if t not in par:
            break
        path, v = [t], t
        while par[v] is not None:
            path.append(par[v])
            v = par[v]
        path.reverse()
        b = min(cap[path[i]][path[i + 1]] for i in range(len(path) - 1))
        for i in range(len(path) - 1):
            cap[path[i]][path[i + 1]] -= b
            cap[path[i + 1]][path[i]] += b
        flow += b
    return flow

MACH = ['甲', '乙', '丙', '丁']
net = {'S': {p: 1 for p in PEOPLE}, 'T': {}}
# TODO: 每个人连向他会开的每台机器，容量 1
# TODO: 每台机器连向 'T'，容量 1

print(str(hungarian(PEOPLE, LIKE)) + "/" + str(maxflow(net, 'S', 'T')))

本次输入：

输出：

👩‍🏫

AI

💬 题目评论

⚠️ 用最大流再算一遍匹配数

更多题目

全部评论