题解

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 100005;

// 并查集父节点数组
int parent[MAXN];

// 查找（路径压缩）
int find(int x) {
    return parent[x] == x ? x : (parent[x] = find(parent[x]));
}

// 边的结构体
struct Edge {
    int u, v, w;
};

// 按美丽度从大到小排序
bool cmp(const Edge& a, const Edge& b) {
    return a.w > b.w;
}

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

    int n, m, K;
    cin >> n >> m >> K;
    vector<Edge> edges(m);
    for (int i = 0; i < m; ++i) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }

    // 初始化并查集
    for (int i = 1; i <= n; ++i) {
        parent[i] = i;
    }

    // 按美丽度降序排序
    sort(edges.begin(), edges.end(), cmp);

    int count = 0;
    int total = 0;
    for (const Edge& e : edges) {
        if (count >= K) break; // 已选够K条边
        int fu = find(e.u);
        int fv = find(e.v);
        if (fu != fv) { // 不连通，选这条边
            parent[fu] = fv;
            total += e.w;
            count++;
        }
    }

    cout << total << endl;
    return 0;
}