⚠️ 把卡住它的那一刀找出来

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

一张管道网，0 号是水源、6 号是出口，每条管子上的数字是每秒最多能过多少水：最大流跑完之后，残量图里从水源还走得到的点已经算进 side 了。把跨出 side 的那些边收成割，输出最大流/割容量/割上有几条边。

提交你的答案

请登录后提交答案。

去登录

← 自己写：把一条增广路灌满 ⚠️ 拆掉一根管子，有时候一点影响都没有 →

更多题目

代码编辑器

语言： 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

f, res = maxflow(CAP, 0, 6)

# 残量图里从源还走得到的那些点，就是割的"源这一侧"
side, st = {0}, [0]
while st:
    u = st.pop()
    for v, c in res[u].items():
        if c > 0 and v not in side:
            side.add(v)
            st.append(v)

cut = []
# TODO: 原图每条边 (u, v)，u 在 side 里而 v 不在，它就在割上
# TODO: 把它的容量收进 cut

print(str(f) + "/" + str(sum(cut)) + "/" + str(len(cut)))

本次输入：

输出：

👩‍🏫

💬 题目评论

⚠️ 把卡住它的那一刀找出来

更多题目

全部评论