79pt #2 #11 #12 求调
查看原帖
79pt #2 #11 #12 求调
1530702
msgjn楼主2025/1/27 15:09
#include <bits/stdc++.h>
#define MAXN 200000
#define MAXM 200001
using namespace std;

struct Edge
{
    int from, to, weight;
    Edge(int _from, int _to, int _weight) : from(_from), to(_to), weight(_weight) {}
    bool operator<(const Edge& edge) const { return weight < edge.weight; }
    bool operator>(const Edge& edge) const { return weight > edge.weight; }
};
int n, m, fa[MAXN], ans = 0, edgeCount = 0;
priority_queue<Edge, vector<Edge>, greater<Edge>> edges;

int find(int id)
{
    if (fa[id] == id)
        return id;
    return (fa[id] = find(fa[id]));
}

bool merge(int a, int b)
{
    int f1 = find(a);
    int f2 = find(b);

    if (f1 == f2)
        return false;

    fa[f1] = f2;
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;

        edges.push(Edge(x, y, z));
    }

    for (int i = 1; i <= n; i++)
        fa[i] = i;

    for (int i = 0; i < edges.size(); i++)
    {
        Edge edge = edges.top();
        edges.pop();

        if (merge(edge.to, edge.from))
        {
            ans += edge.weight;
            edgeCount++;
        }
    }

    if (edgeCount >= n - 1) cout << ans << '\n';
    else cout << "orz\n";

    return 0;
}
2025/1/27 15:09
加载中...