题解 | #Freckles#

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


struct Point{
    double x;
    double y;
};
Point point[100];//1~n

struct Edge{
    double from;
    double to;
    double length;
    bool operator<(const Edge& edge) const{
        return length<edge.length;
    }
};

Edge edge[5000];//0~4999
int father[100];
int height[100];


void Initial()//每个点都作为根节点，高度都为0
{
    for(int i=0;i<100;i++)
    {
        father[i]=i;
        height[i]=0;
    }
}

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

void Union(int a,int b)
{
    a=Find(a);
    b=Find(b);
    if(a!=b)
    {
        if(height[a]>height[b])father[b]=a;
        else  if(height[a]<height[b])father[a]=b;
        else
         {
            father[b]=a;height[a]++;
         }
    }
}

double Kruskal(int n,int enumber)
{
    double answer=0.0;
    for(int i=0;i<enumber;i++)
    {
        if(Find(edge[i].from)!=Find(edge[i].to))
        {
            Union(edge[i].from,edge[i].to);
            answer+=edge[i].length;
        }
    }
    return answer;
}


int main() {
    int n;
    while (cin >> n) { // 注意 while 处理多个 case
        for(int i=1;i<=n;i++)
        {
            cin>>point[i].x>>point[i].y;
        }

        int edgenumber=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=i+1;j<=n;j++)
            {
                edge[edgenumber].from=i;
                edge[edgenumber].to=j;
                edge[edgenumber].length=sqrt((point[i].x-point[j].x)*(point[i].x-point[j].x)+(point[i].y-point[j].y)*(point[i].y-point[j].y));
                edgenumber++;
            }
        }
        sort(edge,edge+edgenumber);
        Initial();
        //
        //for(int i=0;i<n*(n-1)/2;i++)
        //{
        //    cout<<"x:"<<edge[i].from<<"y:"<<edge[i].to<<"      length"<<edge[i].length<<endl;
        //}
        double ans=Kruskal(n,n*(n-1)/2);
        printf("%.2f\n",ans);
    }
}