题解 | #Freckles#

#include <iostream>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;

const int MAXN = 110;
int n;
double x[MAXN], y[MAXN];//x,y为点的坐标
struct Edge {
    int a, b;
    double w;
} edges[MAXN * MAXN]; //声明一个egde结构 保存edge的权值w。a,b 为边的两个节点

int fa[MAXN];// 定义一个整型数组 fa 来存储并查集中每个元素的父亲节点。

int find(int x) {
    if (fa[x] != x) fa[x] = find(fa[x]);
    return fa[x];
}
bool cmp(Edge a, Edge b) {
    return a.w < b.w;
}
double kruskal() {
    for (int i = 1; i <= n; i++) fa[i] = i;//Kruskal 算法的实现。首先初始化并查集，将每个元素的父亲节点设为自身。

    sort(edges + 1, edges + n * (n - 1) / 2 + 1, cmp);

    double ans = 0;
    for (int i = 1; i <= n * (n - 1) / 2; i++) {
        int a = find(edges[i].a), b = find(edges[i].b);
        double w = edges[i].w;

        if (a != b) {
            ans += w;
            fa[a] = b;
        }
    }
    return ans;
}

int main() {
    cin >> n;

    for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];

    int cnt = 0;
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            edges[++cnt] = {i, j, sqrt(pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2))};//计算每两个 freckle 的距离，并存储为一条边。 建立edge集。



    cout << fixed << setprecision(2) << kruskal() << endl;

    return 0;
}