题解 | Freckles 考察并查集、Kruskal

 #include <algorithm>
#include <iostream>
#include <vector>
#include <iomanip>
#include <cmath>
#include <numeric>  // 用于并查集初始化
using namespace std;

struct Point {
    int i;
    double x;
    double y;
};

struct Edge {
    int a;
    int b;
    double distance;
    // Edge(int x, int y, double d):a(x),b(y),distance(d) {}
    bool operator<(const Edge& other) const {
        return distance < other.distance;
    }
};

// 并查集
class UnionFind {
public:
    vector<int> parent;
    UnionFind(int n): parent(n) {
        // iota(): 为parent容器填充递增的序列，从0开始递增
        iota(parent.begin(), parent.end(), 0);
    }

    // 找x的根，如果parent[x]==x表示自己就是根，不等于就继续找父亲的根，
    int find(int x) {
        return parent[x]==x ? x : parent[x]=find(parent[x]);
    }

    bool unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x==y) return false;
        parent[y] = x;
        return true;
    }
};

/*
bool mySort(const Edge& e1, const Edge& e2) {
    return e1.distance<e2.distance;
}
*/

int main() {
    int num;
    while (cin >> num) { // 注意 while 处理多个 case
        vector<Point> points(num);
        for (int i = 0; i<num; i++) {
            points[i].i = i;
            cin >> points[i].x >> points[i].y;
        }
        vector<Edge> edges;
        int cur = 0;
        for (int i = 0; i<num; i++) {
            for (int j = i+1; j<num; j++) {
                double dx = points[i].x - points[j].x;
                double dy = points[i].y - points[j].y;
                double dis = sqrt(dx*dx + dy*dy);
                edges.push_back({points[i].i, points[j].i, dis});
            }
        }
        sort(edges.begin(), edges.end());

        // Kruskal算法求最小生成树
        UnionFind uf(num);
        double sum = 0.0;
        for (const Edge& e: edges) {
            if (uf.unite(e.a, e.b)) {
                sum += e.distance;
            }
        }

        /*
        bool flag[101] = {false};
        for (int i = 0; i<edges.size(); i++) {
            if (flag[edges[i].a] && flag[edges[i].b]) {  //表示边上的2个点在里面
                continue;
            }
            else {
                flag[edges[i].a] = true;
                flag[edges[i].b] = true;
                sum += edges[i].distance;
            }
        } 
        */
        cout << setiosflags(ios::fixed) << setprecision(2) << sum << endl;
        // for (int i = 0; i<edges.size(); i++) {
        //     cout << edges[i].distance << " ";
        // }
    }
}
// 64 位输出请用 printf("%lld")