题解 | #Freckles#

#include <ios>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;

const int MAX = 100;



struct Point {
    int number;
    double x;
    double y;

};

double pointlength(Point x,Point y){
    return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
}

struct Edge{
    Point start;
    Point end;
    double length;
    bool operator<(const Edge e)const{
        return length<e.length;
    }
};

Edge edge[MAX*MAX];
Point point[MAX]; 

int father[MAX];
int height[MAX];

void getedge(int n){
    int k=0;
    for(int i = 0;i<n;++i){
        for(int j = i+1;j<n;++j){
            edge[k].start=point[i];
            edge[k].end=point[j];
            edge[k].length=pointlength(edge[k].start,edge[k].end);
            k++;
        }
    }
}

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

    return;
}

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

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[x]=y;
            height[y]++;
        }
    }
    return ;
}

double Kruskal(int n,int edgenum){
    double sum=0;
    initial(n);
    for(int i= 0 ;i<n;++i){
        cin>>point[i].x>>point[i].y;
        point[i].number=i;
    }
    getedge(n);
    sort(edge,edge+edgenum);
    for(int i = 0;i<edgenum;++i){
        if(find(edge[i].start.number)!=find(edge[i].end.number)){
            Union(edge[i].start.number, edge[i].end.number);
            sum+=edge[i].length;
        }
    }
    return sum;



} 

int main() {
    int n;
    while(cin>>n){
        cout<<setiosflags(ios::fixed)<<setprecision(2)<<Kruskal(n, n*(n-1)/2)<<endl;
    }
}