交付：五条验收条款一起过

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

七个构建任务编号 0~6，(a, b) 表示 a 做完才能做 b：最后一步：把五条验收条款补全，一次全部验过。每一条都落在一个唯一的数上——顺序可以不同，但这些数不能不同。

提交你的答案

请登录后提交答案。

去登录

← 第四步：吞吐量和它的上界「查找」和「匹配」要回答的事差在哪 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

from collections import deque
from itertools import permutations

DEP = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (4, 5), (4, 6)]
G = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (4, 5), (5, 3), (4, 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: {}}
N = 7

def kahn_len(edges):
    g = {u: [] for u in range(N)}
    d = {u: 0 for u in range(N)}
    for a, b in edges:
        g[a].append(b)
        d[b] += 1
    ready = sorted(u for u in range(N) if d[u] == 0)
    out = []
    while ready:
        u = ready.pop(0)
        out.append(u)
        for v in g[u]:
            d[v] -= 1
            if d[v] == 0:
                ready.append(v)
        ready.sort()
    return len(out)

def topo_count(edges):
    return sum(1 for p in permutations(range(N))
               if all(p.index(a) < p.index(b) for a, b in edges))

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

# 五条验收条款，每条都落在一个"唯一的数"上
c1 = kahn_len(DEP) == N          # DAG 排得全
c2 = kahn_len(G) < N             # 有环那张排不全
c3 = None                        # TODO: 合法拓扑序正好 4 种
c4 = None                        # TODO: 这张管道网的最大流正好 7
c5 = None                        # TODO: 前四条全部成立

print("/".join("过" if c else "不过" for c in (c1, c2, c3, c4, c5)))

本次输入：

输出：

👩‍🏫

💬 题目评论

交付：五条验收条款一起过

更多题目

全部评论