交付：五条验收一起过

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

七个构建任务编号 0～6，(a, b) 表示 a 做完才能做 b。

最后一步：把五条验收条款补全，一次全部验过。每一条都落在一个唯一的数上——顺序可以不同，但这些数不能不同。

（本题用 g++ -std=c++17 -O0 编译。）

提交你的答案

请登录后提交答案。

去登录

← 第四步：吞吐量和它的上界大图递归会出什么事 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

#include <algorithm>
#include <climits>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <utility>
#include <vector>
using namespace std;

using Edges = vector<pair<int, int>>;
const int N = 7;
// 七个构建任务，(a, b) 表示 a 做完才能做 b
const Edges DEP = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}, {4, 5}, {4, 6}};
// 同一张图再加一条 5 → 3，于是有了环
const Edges G = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}, {4, 5}, {5, 3}, {4, 6}};

vector<vector<int>> build(const Edges& edges, int n = N) {
    vector<vector<int>> g(n);
    for (auto [a, b] : edges) g[a].push_back(b);
    for (auto& adj : g) sort(adj.begin(), adj.end());
    return g;
}

// Kahn：每次取入度为 0 里编号最小的那个，返回排出来的顺序
vector<int> kahn(const Edges& edges, int n = N) {
    vector<vector<int>> g = build(edges, n);
    vector<int> d(n, 0);
    for (auto [a, b] : edges) d[b]++;
    priority_queue<int, vector<int>, greater<int>> ready;
    for (int u = 0; u < n; u++) {
        if (d[u] == 0) ready.push(u);
    }
    vector<int> out;
    while (!ready.empty()) {
        int u = ready.top();
        ready.pop();
        out.push_back(u);
        for (int v : g[u]) {
            d[v]--;
            if (d[v] == 0) ready.push(v);
        }
    }
    return out;
}

// 枚举全部排列，数一数有几种不违反任何一条依赖
int topo_count(const Edges& edges, int n = N) {
    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    int cnt = 0;
    do {
        vector<int> pos(n);
        for (int i = 0; i < n; i++) pos[p[i]] = i;
        bool ok = true;
        for (auto [a, b] : edges) {
            if (pos[a] > pos[b]) ok = false;
        }
        if (ok) cnt++;
    } while (next_permutation(p.begin(), p.end()));
    return cnt;
}

// 管道网：0 号是水源、6 号是出口，cap[u][v] 是 u→v 这根管子每秒最多过多少水（0 表示没有这根管子）
using Cap = vector<vector<int>>;
Cap make_cap() {
    Cap c(7, vector<int>(7, 0));
    c[0][1] = 6; c[0][2] = 5; c[1][3] = 4; c[1][4] = 2; c[2][4] = 5;
    c[3][6] = 3; c[4][3] = 2; c[4][5] = 4; c[5][6] = 5;
    return c;
}
const Cap CAP = make_cap();

// Edmonds-Karp：反复用 BFS 找一条每段都还有余量的路，把它最细的那一段灌满；res 带回残量图
int maxflow(Cap cap, int s, int t, Cap* res = nullptr) {
    int n = cap.size(), flow = 0;
    for (int round = 0; round < 50; round++) {
        vector<int> par(n, -1);
        par[s] = s;
        queue<int> q;
        q.push(s);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int v = 0; v < n; v++) {
                if (cap[u][v] > 0 && par[v] == -1) {
                    par[v] = u;
                    q.push(v);
                }
            }
        }
        if (par[t] == -1) break;
        int b = INT_MAX;
        for (int v = t; v != s; v = par[v]) b = min(b, cap[par[v]][v]);
        for (int v = t; v != s; v = par[v]) {
            cap[par[v]][v] -= b;
            cap[v][par[v]] += b;
        }
        flow += b;
    }
    if (res) *res = cap;
    return flow;
}

int main() {
    // 五条验收条款，每条都落在一个「唯一的数」上
    bool c1 = (int)kahn(DEP).size() == N;       // DAG 排得全
    bool c2 = (int)kahn(G).size() < N;          // 有环那张排不全
    bool c3 = false;    // TODO: 合法拓扑序正好 4 种（用 topo_count）
    bool c4 = false;    // TODO: 这张管道网的最大流正好 7（用 maxflow）
    bool c5 = false;    // TODO: 前四条全部成立
    vector<bool> cs = {c1, c2, c3, c4, c5};
    for (size_t i = 0; i < cs.size(); i++) cout << (i ? "/" : "") << (cs[i] ? "过" : "不过");
    cout << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

交付：五条验收一起过

更多题目

全部评论