Author: lllyouo
Date: 20250224
tag: 最小生成树
link: https://www.acwing.com/problem/content/1147/

问题描述

link

分析

参考代码

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

const int N = 510;
typedef pair<int, int> PII;

int n, k, fa[N];
PII p[N];

struct Edge {
    int u, v;
    double w;
    
    bool operator< (const Edge& x) {
        return w < x.w;
    }
};
vector<Edge> e;

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

double get_dis(PII a, PII b) {
    int dx = a.first - b.first;
    int dy = a.second - b.second;
    return sqrt(dx * dx + dy * dy);
}

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        int x, y; cin >> x >> y;
        p[i] = {x, y};
    }
    
    for (int i = 0; i < n; i++) fa[i] = i;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            e.push_back({i, j, get_dis(p[i], p[j])});
        }
    }
    sort(e.begin(), e.end());
    
    int cnt = n;
    double ans;
    for (int i = 0; i < e.size(); i++) {
        if (cnt <= k) break;
        
        int fu = find(e[i].u);
        int fv = find(e[i].v);
        
        if (fu != fv) {
            fa[fu] = fv;
            cnt--;
            ans = e[i].w;
        }
    }
    
    printf("%.2lf\n", ans);
    
    return 0;
}