输出 Prim 的加边顺序

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

补全 edges_str：把一组边按顺序写成 a-b，边之间用 / 隔开。输出 Prim 从 0 出发的加边顺序。

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

提交你的答案

请登录后提交答案。

去登录

← 写一个 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}}};

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

MST prim(int n, const vector<vector<int>>& edges, int s) {
    vector<vector<pair<int, int>>> ad(n);       // ad[u] 里放 (w, x)
    for (const auto& e : edges) {
        ad[e[0]].push_back({e[2], e[1]});
        ad[e[1]].push_back({e[2], e[0]});
    }
    vector<bool> seen(n, false);
    seen[s] = true;
    // 堆里放 (权重, 树里那端, 树外那端)，权重小的先出
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
    for (auto [w, v] : ad[s]) pq.push({w, s, v});
    MST r{0, {}};
    int cnt = 1;
    while (!pq.empty() && cnt < n) {
        auto [w, u, v] = pq.top();
        pq.pop();
        if (seen[v]) continue;
        seen[v] = true;
        cnt++;
        r.total += w;
        r.picked.push_back({u, v});
        for (auto [w2, x] : ad[v]) {
            if (!seen[x]) pq.push({w2, v, x});
        }
    }
    return r;
}

string edges_str(const vector<pair<int, int>>& es) {
    // TODO: 按顺序把每条边写成 a-b，边之间用 / 隔开
    (void)es;
    return "";
}

int main() {
    cout << edges_str(prim(5, E5, 0).picked) << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

输出 Prim 的加边顺序

更多题目

全部评论