题解 无线通讯网

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

const int MAXN = 505;

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

int parent[MAXN];
int rank_[MAXN];

void make_set(int v) {
parent[v] = v;
rank_[v] = 0;
}

int find_set(int v) {
if (v == parent[v]) return v;
return parent[v] = find_set(parent[v]);
}

void union_sets(int a, int b) {
a = find_set(a);
b = find_set(b);
if (a != b) {
if (rank_[a] < rank_[b]) swap(a, b);
parent[b] = a;
if (rank_[a] == rank_[b]) rank_[a]++;
}
}

int main() {
int S, P;
cin >> S >> P;
vector<pair<int, int>> points(P);
for (int i = 0; i < P; i++) {
cin >> points[i].first >> points[i].second;
}

vector<Edge> edges;
for (int i = 0; i < P; i++) {
    for (int j = i + 1; j < P; j++) {
        double dx = points[i].first - points[j].first;
        double dy = points[i].second - points[j].second;
        double dist = sqrt(dx * dx + dy * dy);
        edges.push_back({i, j, dist});
    }
}

sort(edges.begin(), edges.end());

for (int i = 0; i < P; i++) {
    make_set(i);
}

int components = P;
double result = 0.0;
for (const Edge& e : edges) {
    if (components <= S) break;
    if (find_set(e.u) != find_set(e.v)) {
        union_sets(e.u, e.v);
        components--;
        result = e.w;
    }
}

cout << fixed << setprecision(2) << result << endl;
return 0;

}