题解 | #Freckles#

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
const int maxn=100;
int father[maxn];
int height[maxn];
struct point{
    float x;
    float y;
    point(float a,float b):x(a),y(b){};
};
struct edge{
    int from;
    int to;
    float length;
    edge(int a,int b,float c):from(a),to(b),length(c){};
    bool operator< (edge o) const{
        return length>o.length;
    }
};
vector<point> store;
priority_queue<edge> q;
void init(){
    store.clear();
    while(!q.empty()){
    	q.pop();
	}
    memset(height,0,sizeof(height));
    for(int i=0;i<maxn;i++) {
	father[i]=i;
}
}
int findfather(int x){
    if(x!=father[x]) father[x]=findfather(father[x]);
    return father[x];
}
void Union(int x,int y){
    x=findfather(x);
    y=findfather(y);
    if(x==y) return;
    if(height[x]>height[y]) father[y]=x;
    else if(height[x]<height[y]) father[x]=y;
    else {
        father[y]=x;
        height[x]++;
    }
}
bool isOneUnion(int n){
    int nums=0;
    for(int i=0;i<n;i++){
        if(i==father[i]) nums++;
    }
    if(nums==1) return true;
    else return false;
}
float krustal(int n){
    float dist=0;
    while(!isOneUnion(n)){
    edge e=q.top();
    q.pop();
    if(findfather(e.from)==findfather(e.to)) continue;
    else {
        Union(e.from,e.to);
        dist+=e.length;}
    }
    return dist;
}
int main(){
    int n;
    while(cin>>n){
        init();
        int p=n;
        while(p>0){
            float x,y;
            cin>>x>>y;
            store.push_back(point(x,y));
            p--;
        }
        for(int i=0;i<store.size();i++){
            for(int j=i+1;j<store.size();j++){
                float l1=pow(store[i].x-store[j].x,2);
                float l2=pow(store[i].y-store[j].y,2);
                float l=pow(l1+l2,0.5);
                q.push(edge(i,j,l));
            }
        }
        cout<<fixed<<setprecision(2)<<krustal(n)<<endl;
    }
}