题解 | #Freckles#

#include <iostream>
#include <queue>
#include <cmath>
#include <algorithm>
#include <iomanip>
#define MAXN 101
using namespace std;
int father[MAXN];//存储每个结点的父节点
int height[MAXN];//每个树的高度
struct Point{
    double x;
    double y;
    Point(double ini_x,double ini_y):x(ini_x),y(ini_y){}
};
double calDistance(Point p1,Point p2){
    return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
struct Edge{
    int from_index;//边的起始下标
    int to_index;//终止下标
    double distance;
    Edge(int from,int to,double ini_distance):from_index(from),to_index(to),distance(ini_distance){}
    inline bool operator < (Edge& g)const{
        return distance<g.distance;
    }
};
int find(int x){//找到x的根
    if(father[x]!=x){
        father[x]=find(father[x]);//递归找到根，并直接让x的父节点为根节点
    }
    return father[x];
}
void Union(int x,int y){
    int findx=find(x);
    int findy=find(y);
    if(findx!=findy){//属于不同连通分量
        if(height[findx]>height[findy]){
            father[findy]=findx;
        }
        else if(height[findx]<height[findy]){
            father[findx]=findy;
        }
        else{//高度相同
            father[findy]=findx;
            height[findx]++;
        }
    }
}
double Kruskal(vector<Edge> edges){
    double res=0;
    for(int i=0;i<edges.size();i++){
        int x=edges[i].from_index;
        int y=edges[i].to_index;
        if(find(x)!=find(y)){//不属于同一个连通分量
            Union(x,y);//合并为一个连通分量
            res+=edges[i].distance;
        }
    }
    return res;
}
int main(){
    int n;
    cin>>n;
    vector<Point> points;
    vector<Edge> edges;
    double res=0;
    for(int i=0;i<n;i++){
        double x,y;
        cin>>x>>y;
        points.push_back(Point(x,y));//存入点信息
    }
    for(int i=0;i<n;i++){//初始化
        father[i]=i;
        height[i]=0;
    }
    for(int i=0;i<n-1;i++){
        for(int j=i+1;j<n;j++){
            double distance;
            distance=calDistance(points[i], points[j]);
            edges.push_back(Edge(i,j,distance));
        }
    }
    sort(edges.begin(),edges.end());
    res=Kruskal(edges);
    cout<<fixed<<setprecision(2)<<res<<endl;
}