题解 | 还是畅通工程

#include <iostream>
#include <map>
#include <algorithm>

using namespace std;

struct Road{
    int _from;
    int _to;
    int _distance;
    bool operator<(const Road& rhs)const{
        return this->_distance < rhs._distance;
    }
};

#define N 5000
Road roads[N] = {0};
map<int,int> father;
map<int,int> height;

int FindRoot(int n){
    if(father[n] != n){
        father[n] = FindRoot(father[n]);
    }
    return father[n];
}

void Union(int n1, int n2){
    int root1 = FindRoot(n1);
    int root2 = FindRoot(n2);
    if(root1 == root2)  // 其实这一句永远执行不到,因为我们是判断之后才合并的
        return ;    // 这两行可以省略   
    // 矮树合并到高树中
    if(height[root1] > height[root2]){
        father[root2] = root1;
    }else if(height[root1] < height[root2]){
        father[root1] = root2;
    }else { // 两棵树一样高
        father[root2] = root1;  // 让2树合并到1树中
        height[root1]++;    // 1树的高度+1
    }
}

int main()
{
    int n;  // 村庄总数
    while(cin >> n &&  n != 0){
        int totalRoad = n*(n-1)/2;
        // 先录入所有路径信息
        for(int i = 0; i < totalRoad; ++i){
            scanf("%d%d%d", &roads[i]._from, &roads[i]._to, &roads[i]._distance);
        }
        // 根据路径信息生成最小生成树
        // 先对路径信息按照distance进行升序排序
        sort(&roads[0],&roads[totalRoad]);
        // 排完序之后按照克鲁斯卡尔算法生成最小生成树
        int sum = 0;
        for(int i = 0; i < totalRoad; ++i){
            int start = roads[i]._from; // 只是因为名字太长,换一个短一点的
            int end = roads[i]._to;
            int dist = roads[i]._distance;
            // 如果该节点为新节点
            if(father.count(start) == 0){
                father[start] = start;  // 以该节点为根节点建树
                height[start] = 1;  // 树高为1
            }
            if(father.count(end) == 0){ // 同上
                father[end] = end;
                height[end] = 1;
            }
            // 到此,两个节点一定都在集合中
            if(FindRoot(start) == FindRoot(end)){   // 两节点已经连通
                continue;   // 直接下一条边
            }else { // 两节点在不同的集合中
                Union(start, end);
                sum += dist;
            }
        }
        cout << sum << endl;
    }

    return 0;
}