题解 | #还是畅通工程#

本题关键在于如何实现克鲁斯卡尔算法。该算法需要将边从小到大进行排序，每次选出不会成环且最小的边，直到边数为节点数减去1，意味着最小生成树生成完成

/*请计算最小的公路总长度。输入描述：测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，
每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。当N为0时，输入结束，该用例不被处理。
输出描述：对每个测试用例，在1行里输出最小的公路总长度。
输入：
3
1 2 1
1 3 2
2 3 4
4
1 2 1
1 3 4
1 4 1
2 3 3
2 4 2
3 4 5
0
输出：
3
5
*/
#include <bits/stdc++.h>

using namespace std;
int father[1010];

void initialize(int n) {
    for (int i = 0; i < n; i++) {
        father[i] = i;
    }
}

int findset(int n) {
    if (n == father[n]) {
        return n;
    } else {
        father[n] = findset(father[n]);
        return father[n];
    }
}

void unionset(int u, int v) {
    int uroot = findset(u);
    int vroot = findset(v);
    father[vroot] = uroot;
}

struct Edge {
    int u, v;
    int weight;

    Edge(int _u, int _v, int _weight) {
        u = _u;
        v = _v;
        weight = _weight;
    }
};
bool compare(Edge lhs,Edge rhs){
    return lhs.weight<rhs.weight;
}
int main() {
    int n,u,v,weight;
    while (scanf("%d",&n)!=EOF) {
        if (n == 0) {
            break;
        }
        vector<Edge> vec;
        initialize(n+1);
        for (int i = 0; i < n*(n-1)/2; i++) {
            scanf("%d%d%d",&u,&v,&weight);
            Edge e(u,v,weight);
            vec.push_back(e); //读取并压入边表型动态数组
        }
        //实现克鲁斯卡尔算法
        sort(vec.begin(),vec.end(), compare);//将各个序列进行升序排序
        int totalweight = 0;
        int curEdgeNum = 0;
        for(int i=0;i<vec.size();i++){
            int u=vec[i].u;
            int v=vec[i].v;
            int weight=vec[i].weight;
            if(findset(u)!=findset(v)){
                unionset(u,v);
                ++curEdgeNum;
                totalweight+=weight;

                if(curEdgeNum==n-1){
                    break;
                }
            }
        }
        printf("%d\n",totalweight);
    }
    return 0;
}