⚠️ 拆掉一根管子，有时候一点影响都没有

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

一张管道网，0 号是水源、6 号是出口，每条管子上的数字是每秒最多能过多少水：把 4 → 3 那根管子整根拆掉，和原来的网各跑一次最大流，再数一数拆完还剩几条管子，三个数一起输出。

提交你的答案

请登录后提交答案。

去登录

← ⚠️ 把卡住它的那一刀找出来 🔴 加粗哪根管子才真的有用 →

更多题目

代码编辑器

语言： 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
    while True:
        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, cap

def drop(cap, u, v):
    out = {}
    for a, d in cap.items():
        out[a] = {b: c for b, c in d.items() if not (a == u and b == v)}
    return out

# TODO: 把 4 → 3 这条管子拆掉，用 drop 造一张新的网
CAP2 = CAP

n2 = sum(len(d) for d in CAP2.values())
print(str(maxflow(CAP, 0, 6)[0]) + "/" + str(maxflow(CAP2, 0, 6)[0]) + "/" + str(n2))

本次输入：

输出：

👩‍🏫

💬 题目评论

⚠️ 拆掉一根管子，有时候一点影响都没有

更多题目

全部评论