Author: lllyouo
Date: 20250225
tag: 最大生成树
link: https://www.luogu.com.cn/problem/P2121

问题描述

link

分析

略

参考代码

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int u, v, w;

    bool operator< (const Edge& x) {
        return w > x.w;
    }
};
vector<Edge> e;
int n, m, k, p[100010];

int find(int x) {
    if (x == p[x]) return x;
    return p[x] = find(p[x]);
}

int main() {
    cin >> n >> m >> k;
    for (int i = 0; i < m; i++) {
        int a, b, c; cin >> a >> b >> c;
        e.push_back({a, b, c});
    }
    sort(e.begin(), e.end());

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

    int ans = 0, cnt = 0;
    for (int i = 0; i < e.size(); i++) {
        int fu = find(e[i].u);
        int fv = find(e[i].v);
        if (fu != fv) {
            p[fu] = fv;
            ans += e[i].w;
            cnt++;
        }
        if (cnt >= k) break;
    }
    cout << ans << endl;
    
    return 0;
}