题解 | Freckles

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=101;
int father[maxn];
int height[maxn];
struct Point{
    float x;
    float y;
    int i;
};
struct Edge{
    float from_x;
    float from_y;
    int i;
    float to_x;
    float to_y;
    int j;
    float weight;
    bool operator<(const Edge& e)const{
        return weight<e.weight;
    }
};
Edge edge[maxn*maxn];
Point point[maxn];
void initial(int n){
    for(int i=0;i<n;i++){
        father[i]=i;
        height[i]=0;
    }
}
int find(int x){
    if(x!=father[x]){
        father[x]=find(father[x]);
    }
    return father[x];
}
void Union(int x,int y){
    x=find(x);
    y=find(y);
    if(x!=y){
        if(height[x]<height[y]){
            father[x]=y;
        }
        else if(height[x]>height[y]){
            father[y]=x;
        }
        else{
            father[y]=x;
            height[x]++;
        }
    }
}
float Kruskal(int n,int edgenumber){
    initial(n);
    sort(edge,edge+edgenumber);
    float answer;
    for(int i=0;i<edgenumber;i++){
        if(find(edge[i].i)!=find(edge[i].j)){
            answer+=edge[i].weight;
            Union(edge[i].i,edge[i].j);
        }
    }
    return answer;
}
int main(){
    int n;
    while(cin>>n){
        for(int i=0;i<n;i++){
            cin>>point[i].x>>point[i].y;
            point[i].i=i;
        }
        int k=0;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                edge[k].from_x=point[i].x;
                edge[k].from_y=point[i].y;
                edge[k].to_x=point[j].x;
                edge[k].to_y=point[j].y;
                edge[k].i=point[i].i;
                edge[k].j=point[j].i;
                edge[k].weight=sqrt((point[j].x-point[i].x)*(point[j].x-point[i].x)+(point[j].y-point[i].y)*(point[j].y-point[i].y));
                k++;
            }
        }
        int edgenumber=n*(n-1)/2;
        printf("%.2f\n",Kruskal(n,edgenumber));
    }
}