题解 | #Freckles#

//考点最小生成树
//用到并查集和Kruskal算法
//注意输出格式要求
#include <ios>
#include <iostream>
#include<vector>
#include<algorithm>
#include<math.h>
using namespace std;
//最小生成树
//并查集
int father[1000];
void InitDisjointSet(int n){
    for(int i=0;i<n;i++){
        father[i]=i;
    }
}
int FindrootDisjointSet(int n){
    if(father[n]==n){
        return father[n];
    }
    else{
        father[n]=FindrootDisjointSet(father[n]);
        return father[n];
    }
}
void UnionDisjointSet( int u,int v){
    int u_root=FindrootDisjointSet(u);
    int v_root=FindrootDisjointSet(v);
    father[v_root]=u_root;
}
struct vertex{//顶点
    float x;
    float y;
};
struct edge{//边
    int vertex1;
    int vertex2;
    float length;
};
bool compare(edge e1,edge e2){//sort
    return e1.length<e2.length;
}
int main() {
    int n;
    while (cin >> n) {
	  //输入顶点集
        vector<vertex>vertexarr(101);
        vector<edge> edgearr;
        for(int i=0;i<n;i++){
            cin>>vertexarr[i].x>>vertexarr[i].y;
        }
        for(int i=0;i<n;i++){//构造边集
            for(int j=i+1;j<n;j++){
                edge e;
                e.vertex1=i;
                e.vertex2=j;
                e.length=sqrt(pow(vertexarr[i].x-vertexarr[j].x,2)+pow(vertexarr[i].y-vertexarr[j].y,2));
                edgearr.push_back(e);
            }
        }
        sort(edgearr.begin(),edgearr.end(),compare);//升序
        InitDisjointSet(n);
        float TotalLength=0;
        int curedgenum=0;
        for(int i=0;i<edgearr.size();i++){//Kruskal
            int u=edgearr[i].vertex1;
            int v=edgearr[i].vertex2;
            if(FindrootDisjointSet(u)!=FindrootDisjointSet(v)){
                curedgenum++;
                UnionDisjointSet(u,v);
                TotalLength+=edgearr[i].length;
                if(curedgenum==n-1){
                    break;
                }
            }
        }
        cout<<fixed;
        cout.precision(2);
        cout << TotalLength << endl;
    }
}