本文共 2354 字，大约阅读时间需要 7 分钟。

这段代码实现了一个最小生成树算法，结合了并查集（Union-Find）数据结构。以下是对代码的详细分析和解释：

代码结构

代码解释

• 预定义部分：

  #include 
       
        #define maxn 10005using namespace std;
       

  包含了必要的头文件，定义了节点数的最大值 maxn。

• 结构体定义：

  struct node {    int from, to;    double val;}

  用于存储边的信息，包括起点、终点和权重。

• 比较函数：

  bool cmp(node a, node b) {    return a.val < b.val;}

  用于对边按权重排序。

• 初始化函数：

  void init() {    for (int i = 1; i <= maxn; ++i) {        pre[i] = i;    }}

  初始化每个节点的父节点为自身。

• 查找函数：

  int find(int x) {    if (pre[x] != x) {        pre[x] = find(pre[x]);    }    return pre[x];}

  查找节点 x 的根节点，并进行路径压缩。

• 合并函数：

  bool join(int x, int y) {    int fx = find(x);    int fy = find(y);    if (fx != fy) {        pre[fx] = fy;        return true;    }    return false;}

  将节点 x 和 y 合并到同一个集合中。

• 主函数：

  int main() {    int T;    cin >> T;    while (T--) {        init();        int n;        cin >> n;        for (int i = 1; i <= n; ++i) {            cin >> xx[i] >> yy[i];        }        int num = 0;        for (int i = 1; i <= n; ++i) {            for (int j = i + 1; j <= n; ++j) {                double dis = sqrt(pow(xx[i] - xx[j], 2) + pow(yy[i] - yy[j], 2));                if (dis >= 10 && dis <= 1000) {                    path[num].from = i;                    path[num].to = j;                    path[num].val = dis;                    ++num;                }            }        }        sort(path, path + num, cmp);        double ans = 0.0;        for (int i = 0; i < num; ++i) {            if (join(path[i].from, path[i].to)) {                ans += path[i].val;            }        }        int mark = 0;        bool flag = false;        for (int i = 1; i <= n; ++i) {            if (pre[i] == i) {                mark++;            }        }        if (mark > 1) {            flag = true;        }        if (flag) {            printf("oh!\n");        } else {            printf("%.1lf\n", ans * 100);        }    }    return 0;}

  读取输入数据，计算所有可能的边，并存储在 path 数组中。对边进行排序后，使用并查集逐一合并边，直到所有节点连成一棵树。最后计算最小生成树的总权重。

代码优化建议

• 路径压缩：在 find 函数中使用路径压缩优化查找和并查集性能。
• 按权重排序：确保边是按权重从小到大排序，以保证Kruskal算法正确性。
• 终止条件：检查是否所有节点连通，避免重复计算或错误输出。

通过以上分析和优化，可以更好地理解和使用这段代码实现的最小生成树算法。

转载地址：http://fxaq.baihongyu.com/