题解 | #Freckles#

#include<cstdio>
#include<vector>
#include<algorithm>
#include<math.h>
#include<iostream>
#define N 101
using namespace std;
float  res;
struct point {//定义点集
    float x;
    float y;
};
struct G { //图，起点终点 ，距离
    int from;
    int to;
    float weight;
};

vector<point> vec;
vector<G> graph;
//并查集，在合并的时候求距离
int father[N];
int height[N];
float distance(point lhs, point rhs) {//算两点之间距离之和
    return pow(pow((lhs.x - rhs.x), 2) + pow((lhs.y - rhs.y), 2), 0.5);
}
void Init(int n) {//初始化并查集和两个集合
    for (int ic = 0 ; ic < n; ++ic) {
        father[ic] = ic ;
        height[ic] = 0;
    }
    graph.clear();
    vec.clear();
    res = 0;
}
int Find(int x) {//查
    if (x != father[x]) {
        return Find(father[x]);
    } else {
        return father[x];
    }
}
void Union(int x, int y, float weight) {//并
    x = Find(x);
    y = Find(y);
    if (x == y) {
        res = res;
    } else {
        res += weight;
        if (height[x] > height[y]) {
            father[y] = x;
        } else if (height[y] > height[x]) {
            father[x] = y;
        } else {
            father[x] = y;
            ++ height[y] ;
        }
    }
}
bool comp(G lhs, G rhs) {//按权值从小到大排列
    if (lhs.weight < rhs.weight) {
        return  true;
    } else {
        return false;
    }
}
int main() {
    int n;
    point p;
    G g;
    scanf("%d", &n);
    Init(n);
    for (int iw = 0 ; iw < n ; ++iw) {
        cin >> p.x >> p.y; //传入点
        vec.push_back(p);
    }
    for (int ix = 0 ; ix < n - 1 ; ++ix) {
        for (int j = ix + 1 ; j < n ; ++j) {
            g.from = ix;
            g.to = j;
            g.weight = distance(vec[ix], vec[j]);
            graph.push_back(g);
        }
    }
    sort(graph.begin(), graph.end(), comp);
    for (int idx = 0 ; idx < graph.size() ; ++idx) {
        Union(graph[idx].from, graph[idx].to, graph[idx].weight);
    }
    printf("%.2f\n", res);
}