Kruskal 和暴力必须一致

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

Kruskal 写好了，补全暴力枚举 brute_mst，在同一组边上各求一次最小总长。输出三样：Kruskal 的答案 / 暴力的答案 / 是否相同（相同输出结果一致，否则结果不一致）。

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

提交你的答案

请登录后提交答案。

去登录

← Kruskal 按什么顺序选边 Prim 的做法 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

#include <algorithm>
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

typedef long long ll;
const ll INF = 1000000000;                       // 走不到的点记这个值，输出时写成 -1
using Graph = vector<vector<pair<int, int>>>;    // g[u] 里放 (邻居 v, 边权 w)

// 七个点的无向图（和 Python 版同一组数据）：0-1:2 0-2:1 1-3:3 2-4:9 3-4:1 5-6:7
const vector<vector<int>> E7 = {{0, 1, 2}, {0, 2, 1}, {1, 3, 3}, {2, 4, 9}, {3, 4, 1}, {5, 6, 7}};
// 主连通块五个点、五条边（求最小生成树用）
const vector<vector<int>> E5 = {{0, 1, 2}, {0, 2, 1}, {1, 3, 3}, {2, 4, 9}, {3, 4, 1}};
// 有向负权反例：0→1:4 0→2:5 2→1:-3 1→3:1
const Graph NEG = {{{1, 4}, {2, 5}}, {{3, 1}}, {{1, -3}}, {}};
// 同一张图，只把 2→1 那条边改成 +3
const Graph POS = {{{1, 4}, {2, 5}}, {{3, 1}}, {{1, 3}}, {}};
// 有负环：0→1:1 1→2:-1 2→1:-1
const Graph CYC = {{{1, 1}}, {{2, -1}}, {{1, -1}}};

vector<int> make_set(int n) {
    vector<int> p(n);
    for (int i = 0; i < n; i++) p[i] = i;
    return p;
}

int find_root(vector<int>& p, int x) {
    while (p[x] != x) {
        p[x] = p[p[x]];      // 路径压缩：挂到爷爷上
        x = p[x];
    }
    return x;
}

bool unite(vector<int>& p, int a, int b) {
    // 两端已在同一块里就返回 false（这条边会成环）
    int ra = find_root(p, a), rb = find_root(p, b);
    if (ra == rb) return false;
    p[ra] = rb;
    return true;
}

struct MST {
    ll total;
    vector<pair<int, int>> picked;
};

MST kruskal(int n, vector<vector<int>> edges) {
    // 按 (权重, 两端编号) 从小到大排，union 成功才要这条边
    sort(edges.begin(), edges.end(), [](const vector<int>& x, const vector<int>& y) {
        if (x[2] != y[2]) return x[2] < y[2];
        if (x[0] != y[0]) return x[0] < y[0];
        return x[1] < y[1];
    });
    vector<int> p = make_set(n);
    MST r{0, {}};
    for (const auto& e : edges) {
        if (unite(p, e[0], e[1])) {
            r.total += e[2];
            r.picked.push_back({e[0], e[1]});
        }
    }
    return r;
}

ll brute_mst(int n, const vector<vector<int>>& edges) {
    ll best = INF;
    // TODO: 用 mask 枚举边的子集，只看恰好 n-1 条边的；用并查集判断有没有成环，
    //       没成环就是一棵生成树，取总长最小的那棵
    (void)n; (void)edges;
    return best;
}

string verdict(ll a, ll b) {
    return a == b ? "结果一致" : "结果不一致";
}

int main() {
    ll a = kruskal(5, E5).total, b = brute_mst(5, E5);
    cout << a << "/" << b << "/" << verdict(a, b) << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

Kruskal 和暴力必须一致

更多题目

全部评论