洛谷题单<最小生成树> 无线通讯网

水题 直接kruskal 加边数 == p - s 返回边长即可
代码如下

#include<bits/stdc++.h>
using namespace std;
const int N = 510;

int s, p;

struct edge{
    int a, b;
    double c;
    bool operator<(const edge & w)const{
        return c < w.c;
    }
}edges[N * N];//完全图 
struct node{
    int x, y;
}node[N];

int pp[N];//并查集 

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

double kruskal(int n){
    for(int i = 1; i <= p; i++) pp[i] = i;
    int res = 0;
    for(int i = 0; i < n; i ++){
        int a = edges[i].a, b = edges[i].b;
        double z = edges[i].c;
        int x = find(a), y = find(b);
        if(x != y){
            res ++;
            if(res == p - s) return z; //退出循环 
            pp[x] = y;
        }
    }
}


int main(){
    cin >> s >> p;
    for(int i = 1; i <= p; i++){
        int a, b;
        scanf("%d%d", &a, &b);
        node[i] = {a, b};
    }    
    int cnt = 0;
    for(int i = 1; i <= p; i++){
        for(int j = i + 1; j <= p; j++){
            double z = sqrt((node[i].x-node[j].x)*(node[i].x-node[j].x)+(node[i].y-node[j].y)*(node[i].y-node[j].y));
            edges[cnt++] = {i, j, z};
        }
    }

    sort(edges, edges + cnt);
    double D = kruskal(cnt);

    printf("%.2f", D);
}