题解 | #Freckles 并查集#

#include "bits/stdc++.h"
using namespace std;
int father[5000];
int height[5000];
struct Edge{
    int begin;
    int end;
    double cost;
};
struct Point{
    double x;
    double y;
};
void Inti(){
    for (int i = 0; i < 5000; ++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){
    int x_father = Find(x);
    int y_father = Find(y);
    if(height[x_father]>height[y_father]){
     father[y_father] = x_father;
    } else if(height[x_father]<height[y_father]){
        father[x_father] = y_father;
    }else{
        father[y_father] = x_father;
        height[x_father]++;
    }
}

bool compare1(Edge x,Edge y){
    return x.cost<y.cost;
}
int main() {
    int n;
    while (scanf("%d",&n)!=EOF){
        if(n==0){ break;}
        Inti();
        double answer = 0;
        Edge edge[n*(n-1)/2];
        Point points[n];
        for (int i = 0; i < n; ++i) {
            scanf("%lf%lf",&points[i].x,&points[i].y);
        }
        int count=0;
        for (int i = 0; i < n; ++i) {
            for (int j = i+1; j < n; ++j) {
                edge[count].begin=i;
                edge[count].end=j;
                edge[count].cost = sqrt((points[i].x-points[j].x)*(points[i].x-points[j].x)+(points[i].y-points[j].y)*(points[i].y-points[j].y));
                count++;
            }
        }
        sort(edge,edge+n*(n-1)/2,compare1);
        for (int i = 0; i < n*(n-1)/2; ++i) {
            if(Find(edge[i].begin)!=Find(edge[i].end)){
                Union(edge[i].begin,edge[i].end);
                answer+=edge[i].cost;
            }
        }
        printf("%.2lf\n",answer);

    }
    return 0;
}