点数翻倍代价翻几倍

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

点数从 7 涨到 14，边数也跟着差不多翻倍。算一算拓扑排序在两种规模下各做多少次减法。

（本题用 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>>;

vector<vector<int>> build(const Edges& edges, int 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;
}

// 一条链再挂几个旁支，边数大约是点数的一倍多
Edges edges_of(int n) {
    Edges e;
    for (int i = 0; i + 1 < n; i++) e.push_back({i, i + 1});
    for (int i = 2; i < n; i += 3) e.push_back({0, i});
    return e;
}

// 数一数 Kahn 里「入度减 1」一共做了多少次
int kahn_cost(const Edges& edges, int 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);
    }
    int steps = 0;
    while (!ready.empty()) {
        int u = ready.top();
        ready.pop();
        for (int v : g[u]) {
            d[v]--;
            steps++;
            if (d[v] == 0) ready.push(v);
        }
    }
    return steps;
}

int main() {
    // TODO: 分别算出 7 个点和 14 个点两种规模下的减法次数，放进 a 和 b
    int a = -1, b = -1;
    cout << a << "/" << b << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

点数翻倍代价翻几倍

更多题目

全部评论