题解 | Freckles

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn = 105;
int f[maxn];
int h[maxn];
void init() {
    for (int i = 0; i < maxn; i++) {
        f[i] = i;
        h[i] = 0;
    }
}
int find(int x) {
    if (x != f[x]) {
        f[x] = find(f[x]);
    }
    return f[x];
}
void uniond(int x, int y) {
    x = find(x);
    y = find(y);
    if (x != y) {
        if (h[x] > h[y])f[y] = x;
        else if (h[x] < h[y])f[x] = y;
        else {
            f[y] = x;
            h[x]++;
        }
    }
}
struct edge {
    double x;
    double y;
    int num;
} ed[maxn];
struct path {
    int from;
    int to;
    double len;
} pa[maxn * maxn];
bool cmp(path p1, path p2) {
    return p1.len < p2.len;
}
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> ed[i].x >> ed[i].y;
        ed[i].num = i;
    }
    int k = 0;
    for (int i = 0; i < n - 1;
            i++) { //i点到j点都有路线，测出每一条路线
        for (int j = i + 1; j < n; j++) {
            pa[k].from = i;
            pa[k].to = j;
            double x1 = abs(ed[i].x - ed[j].x);
            double y1 = abs(ed[i].y - ed[j].y);
            pa[k].len = sqrt(x1 * x1 + y1 * y1);
            k++;
        }
    }
    sort(pa, pa + k, cmp);
    double sum = 0;
    init();
    for (int i = 0; i < k; i++) {
        if (find(pa[i].from) != find(pa[i].to)) {
            uniond(pa[i].from, pa[i].to);
            sum += pa[i].len;
        }
    }
    printf("%.2f\n", sum);
}