第四步：吞吐量和它的上界

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

一张管道网，0 号是水源、6 号是出口，每条管子上的数字是每秒最多能过多少水：第四步：算出这张网的最大流，再算出水源接出去的总容量，两个一起输出。

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 out_of(cap, s):
    return sum(cap[s].values())

# TODO: 算出最大流，以及水源接出去的总容量
f, o = -1, -1

print(str(f) + "/" + str(o))

本次输入：

输出：

👩‍🏫

💬 题目评论

第四步：吞吐量和它的上界

更多题目

全部评论