题解 | #Freckles#

#include <iostream>
#include <cmath>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

double getdist(double x1, double y1, double x2, double y2) {
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

typedef pair<double, double> PII;

map<PII, PII> p;
map<PII, int> h;

struct Edge {
    PII p1;
    PII p2;
    double w;
    Edge (PII x, PII y, double z): p1(x), p2(y), w(z) {};
    bool operator < (const Edge& e) const {
        return w < e.w;
    }

};

PII find(PII point) {
    if (point != p[point])p[point] = find(p[point]);
    return p[point];
}

void punion(PII a, PII b) {
    PII x = find(a);
    PII y = find(b);
    if (x != y) {
        if (h[x] > h[y]) {
            p[y] = x;
        } else if (h[x] < h[y]) {
            p[x] = y;
        } else {
            p[x] = y;
            h[y]++;
        }
    }
    return ;
}

double kruskal(vector<Edge> edges){
    double ans=0;
    for(int i=0;i<edges.size();i++){
        PII x = edges[i].p1;
        PII y = edges[i].p2;
        if(find(x)!=find(y)){
            ans+=edges[i].w;
            punion(x, y);
        }
    }

    return ans;
}

int main() {
    int n;
    cin >> n;
    vector<PII> points;
    vector<Edge> edges;

    while (n--) {
        double x, y;
        cin >> x >> y;
        if (p.find({x, y}) == p.end()) {
            h.insert({{x, y}, 0});
            p.insert({{x, y}, {x, y}}); //初始化并查集
        }
        points.push_back({x, y});
    }
    n = points.size();
    //cout<<points.size()<<endl;
    for (int i = 0; i < n - 1; i++) {
        PII p1 = points[i];
        for (int j = i + 1; j < n; j++) {
            PII p2 = points[j];
            double w = getdist(p1.first, p1.second, p2.first, p2.second);
            edges.push_back(Edge(p1, p2, w));
        }
    }
    sort(edges.begin(), edges.end());
    //cout<<edges.size()<<endl;
    double ans = kruskal(edges);
   printf("%.2lf",ans);
    return 0;
}