题解 | #Freckles#

// 克鲁斯卡尔算法
// 计算任意两点间的距离，并记录每条边，编号【0 - n-1】
// 对于边的集合进行排序，从小到大
// （克鲁斯卡尔算法）依次遍历所有边，使用并查集判断是否处于同一集合，不属于一个集合就记录该边
// 当连通分量=1时，输出
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

struct Dot
{
    int id; // 编号，re0
    double x;
    double y;
};

struct Edge
{
    int from;
    int to;
    double length;
};

vector<Dot> dot;
vector<Edge> edge;

// 并查集 start
const int maxn = 100;
int father[maxn];
int height[maxn];
void init(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]++;
        }
    }
}
int countFather(int n)
{
    int count = 0;
    for (int i = 0; i < n; i++)
    {
        if (find(i) == i)
            count++;
    }
    return count;
}
// 并查集 end

bool comp(Edge x,Edge y){
    return x.length<y.length;
}

int n,num_of_edge;//结点数  边数

int main(){
    while (cin>>n)
    {
        if(n==0) break;
        double x,y;
        for(int i=0;i<n;i++){
            cin>>x>>y;
            Dot d;
            d.id=i;  //进入vector顺序即编号，可不用id
            d.x=x;
            d.y=y;
            dot.push_back(d);
        }//处理输入

        //每两个结点构成一条边
        num_of_edge=n*(n-1)/2;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                Edge e;
                e.from=i;
                e.to=j;
                e.length=sqrt((dot[i].x-dot[j].x)*(dot[i].x-dot[j].x)+(dot[i].y-dot[j].y)*(dot[i].y-dot[j].y));
                edge.push_back(e);
            }
        }
        //对边从小到大排序
        sort(edge.begin(),edge.end(),comp);

        init(n);
        double ans=0;
        for(int i=0;i<edge.size();i++){
            if(find(edge[i].from) != find(edge[i].to)){
                Union(edge[i].from , edge[i].to);
                ans+=edge[i].length;
            }
            if(countFather(n)==1){
                break;
            }
        }//kruskal算法

        printf("%.2f",ans);
    }
}