🔴 加粗哪根管子才真的有用

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

一张管道网，0 号是水源、6 号是出口，每条管子上的数字是每秒最多能过多少水：给你一次加粗的机会。分别试试加粗最细的那根（1 → 4，从 2 到 4）和加粗割上的那根（3 → 6，从 3 到 5），连同原始值一起输出三个数。

CAP = {0: {1: 6, 2: 5}, 1: {3: 4, 4: 2}, 2: {4: 5},
       3: {6: 3}, 4: {3: 2, 5: 4}, 5: {6: 5}, 6: {}}

提交你的答案

请登录后提交答案。

去登录

← ⚠️ 拆掉一根管子，有时候一点影响都没有什么样的问题能套二分图匹配 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

from collections import deque

CAP = {0: {1: 6, 2: 5}, 1: {3: 4, 4: 2}, 2: {4: 5},
       3: {6: 3}, 4: {3: 2, 5: 4}, 5: {6: 5}, 6: {}}

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

def bump(u, v, nc):
    c = {a: dict(b) for a, b in CAP.items()}
    c[u][v] = nc
    return c

# TODO: 第二个数：把最细的那根 1 → 4 从 2 加粗到 4，再算一次
# TODO: 第三个数：把割上的 3 → 6 从 3 加粗到 5，再算一次
a = maxflow(CAP, 0, 6)
b, c = -1, -1

print(str(a) + "/" + str(b) + "/" + str(c))

本次输入：

输出：

👩‍🏫

💬 题目评论

🔴 加粗哪根管子才真的有用

更多题目

全部评论