题解 | #Freckles#

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

int father[1010];
int height[1010];

struct Dot {
    double x;
    double y;
};

struct Edge {
    int from;
    int to;
    double weight;
};

vector<Dot> v;
vector<Edge> G;

void Init(int n) {
    for (int i = 1; i <= n; i++) {
        father[i] = i;
        height[i] = 1;
    }
}


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


void Union(int x, int y, double weight, double &total) {
    x = find(x);
    y = find(y);
    if (x != y) {
        total += weight;
        if (height[x] < height[y]) {
            father[x] = y;
        } else if (height[x] > height[y]) {
            father[y] = x;
        } else {
            father[y] = x;
            height[x]++;
        }
    }

}

double getdis(Dot x, Dot y) {
    return pow((x.x - y.x) * (x.x - y.x) + (x.y - y.y) * (x.y - y.y), 0.5);
}

bool compare(Edge l, Edge r) {
    return l.weight < r.weight;
}


int main() {
    int n;
    scanf("%d", &n);
    Init(n);
    for (int i = 0; i < n; i++) {
        Dot d;
        scanf("%lf%lf", &d.x, &d.y);
        v.push_back(d);
    }
    for (int i = 0; i < v.size() - 1; i++) {
        Edge edge;
        for (int j = i + 1; j < v.size(); j++) {
            edge.from = i;
            edge.to = j;
            edge.weight = getdis(v[i], v[j]);
            G.push_back(edge);
        }
    }
    sort(G.begin(), G.end(), compare);
    double total = 0;
    for (int i = 0; i < G.size(); i++) {
        Union(G[i].from, G[i].to, G[i].weight, total);
    }
    printf("%.2lf\n", total);
    return 0;
}