解题思路

本题要求设计一个网络连接，使得给定区域内的所有点相互连通，且所用电缆总长度最短。

1. 数据结构定义：

   • 定义结构体node，用于存储每条路线的起点u、终点v和长度w。
   • 重载<运算符，以便在优先队列中按长度从小到大排序。
   • 定义并查集数组fa[55]，用于判断两个点是否在同一连通分量中。

2. 输入处理：

   • 读取输入的点的数量p和路线数量r。
   • 初始化并查集，使每个点的父节点为其自身。
   • 将每条路线的信息读入并加入优先队列q。

3. 最小生成树构建：

   • 初始化计数器cnt为0，结果变量res为0。
   • 当计数器cnt小于p - 1时（因为一个连通图的最小生成树边数为n - 1，这里n为点数），执行以下操作：
     • 从优先队列中取出长度最小的路线node t。
     • 取出该路线的起点u、终点v和长度w。
     • 使用并查集判断u和v是否在同一连通分量中，如果是则跳过该路线（因为加入该路线会形成环）。
     • 否则，将u和v所在的连通分量合并（通过Union函数），并将该路线的长度w累加到结果变量res中，同时计数器cnt加1。

4. 输出结果：

   • 循环结束后，输出结果变量res，即设计网络所用电缆的总长度。

#include<iostream>
#include<queue>
using namespace std;

struct node{
    int u, v, w;
    node(int a, int b, int c) : u(a), v(b), w(c) {}
};

bool operator < (const node &a, const node &b) {
    return a.w > b.w;
}

int p, r, fa[55], set_rank[55]; // 重命名为 set_rank，避免与 std::rank 冲突

int find(int x) {
    if (fa[x] == x)
        return x;
    return fa[x] = find(fa[x]); // 路径压缩
}

void Union(int x, int y) {
    int m = find(x), n = find(y);
    if (m != n) {
        if (set_rank[m] < set_rank[n])  // 使用 set_rank 代替 rank
            fa[m] = n;
        else if (set_rank[m] > set_rank[n])  // 使用 set_rank 代替 rank
            fa[n] = m;
        else {
            fa[n] = m;
            set_rank[m]++;  // 使用 set_rank 代替 rank
        }
    }
}

int main() {
    while (cin >> p && p) {
        cin >> r;
        if (p < 1 || p > 50 || r < 0) {
            cerr << "输入数据无效" << endl;
            return 1;
        }
        
        for (int i = 1; i <= p; i++) {
            fa[i] = i;
            set_rank[i] = 0;  // 使用 set_rank 代替 rank
        }
        
        priority_queue<node> q;
        for (int i = 0; i < r; i++) {
            int x, y, z;
            if (!(cin >> x >> y >> z)) {
                cerr << "输入数据格式错误" << endl;
                return 1;
            }
            if (x < 1 || x > p || y < 1 || y > p || z < 0 || z > 100) {
                cerr << "输入数据无效" << endl;
                return 1;
            }
            q.push(node(x, y, z));
        }
        
        int cnt = 0, res = 0;
        while (cnt < p - 1 && !q.empty()) {
            node t = q.top();
            q.pop();
            int u = t.u, v = t.v, w = t.w;
            if (find(u) == find(v))
                continue;
            
            Union(u, v);
            res += w;
            cnt++;
        }
        
        if (cnt < p - 1) {
            cerr << "无法连接所有点" << endl;
            return 1;
        }
        
        cout << res << endl;
    }
    return 0;
}