北极通讯网络

LibreOJ-10065-北极通讯网络

实现

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

const int N = 510, M = N * N / 2;
struct edge {
    int u, v;
    double w;
    bool operator < (const edge& o) const {
        return w < o.w;
    }
};
struct node {
    int x, y;
};
int n, m, k;
node a[N];
edge e[M];
int f[N];

double dis (const node& a, const node& b) {
    int dx = a.x - b.x, dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}
int find (int x) {
    if (f[x] == x) return x;
    return f[x] = find(f[x]);
}
void merge (int x, int y) {
    f[find(x)] = find(y);
}
bool query (int x, int y) {
    return find(x) == find(y);
}
double kruskal () {
    for (int i = 1; i <= n; ++ i) f[i] = i;
    sort(e + 1, e + m + 1);
    double res = 0;
    int cnt = n;
    for (int i = 1; i <= m; ++ i) {
        int u = e[i].u, v = e[i].v;
        double w = e[i].w;

        if (query(u, v) == false) {
            merge(u, v);
            res = w;
            if (-- cnt <= k) break;
        }
    }
    return res;
}

int main () {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++ i) scanf("%d%d", &a[i].x, &a[i].y);

    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j < i; ++ j)
            e[++ m] = { i, j, dis(a[i], a[j]) };
    printf("%.2lf", kruskal());
    return 0;
}