题解 | #Freckles#

#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
struct cmp{
    bool operator()(const pair<float,pair<int,int>> &a,const pair<float,pair<int,int>> &b){
        return a.first > b.first;
    }
};
float cal(pair<float,float> a,pair<float,float> b){
    return sqrt(fabs(a.first - b.first) * fabs(a.first - b.first) + fabs(a.second - b.second) * fabs(a.second - b.second));
}
int find(int x,vector<int> father){
    if(x != father[x])
        father[x] = find(father[x],father);
    return father[x];
}
void clear(priority_queue<pair<float,pair<int,int>>,vector<pair<float,pair<int,int> >>,cmp>& q) {
    priority_queue<pair<float,pair<int,int>>,vector<pair<float,pair<int,int> >>,cmp> empty;
    swap(empty, q);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,edgenum;
    float x,y,dist;
    vector<int> father;
    vector<pair<float,float>> vec;
    priority_queue<pair<float,pair<int,int>>,vector<pair<float,pair<int,int> >>,cmp> qu;
    while(cin >> n){
        father.clear();
        vec.clear();
        clear(qu);
        while(n--){
            cin >> x >> y;
            vec.push_back(pair<float,float>(x,y));
        }
        for(int i = 0;i < vec.size();++i){
            for(int j = i + 1;j < vec.size();++j){
                qu.push(pair<float,pair<int,int>>(cal(vec[i],vec[j]),pair<int,int>(i,j)));
            }
        }
        for(int i = 0;i < vec.size();++i)
            father.push_back(i);
        dist = 0;
        edgenum = 0;
        while(edgenum < vec.size() - 1 && !qu.empty()){
            auto cur = qu.top();
            qu.pop();
            int f = cur.second.first;
            int t = cur.second.second;
            f = find(f,father);
            t = find(t,father);
            if( f != t ){
                father[f] = t;
                dist += cur.first;
                edgenum++;
            }
        }
        printf("%.2f\n",dist);
    }
}