题解 | 还是畅通工程

思路：构造最小生成树，即保证所有顶点连通（间接也可以）+边的权值最小。

可用克鲁斯克拉算法求生成树：每次选权值最小的边，判断若边所在的两个顶点不连通则加入树中，否则跳过该边，

一直到树构建完成（特征是边数=顶点个数-1）。

#include <cstring>
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int father[1010];
//初始化
void Initfun(int n) {
    for (int i = 1; i < n; i++) {
        father[i] = i;
    }
    return;
}
//找根结点
int FindFather(int i) {
    if (i == father[i]) {//根节点
        return i;
    } else {
        father[i] = FindFather(father[i]);
        return father[i];
    }
}
//合并并查集
void UniteSet(int a, int b) {
    if (FindFather(a) == FindFather(b)) {
        return;
    } else {
        father[FindFather(a)] = FindFather(
                                    b);//注意不是a，b直接相连，是两者的根相连
    }
    return;
}
struct Edge {
    int a;
    int b;
    int weigth;
    Edge(int a_, int b_, int weigth_) {
        a = a_;
        b = b_;
        weigth = weigth_;
    }
};
bool compare(Edge l, Edge r) {
    return l.weigth < r.weigth;
}
int main() {
    int N, a, b, w;
    while (scanf("%d", &N) != EOF) {
        if (N == 0) {
            break;
        }
        Initfun(N);
        int edge = 0;
        int minLen = 0;
        vector<Edge> vec;
        for (int i = 0; 2 * i < N * (N - 1); i++) {
            scanf("%d%d%d", &a, &b, &w);
            Edge e(a, b, w);
            vec.push_back(e);

        }
        //对边的权值（距离）进行升序排列
        sort(vec.begin(), vec.end(), compare);
        //构建最小生成树（克鲁斯克拉算法）
        vector<int> visited(N, 0);
        //每次选择最小的边
        for (int i = 0; i < vec.size(); i++) {
            if (FindFather(vec[i].a) != FindFather(vec[i].b)) {
                //若顶点不连通则加入并查集
                UniteSet(vec[i].a, vec[i].b);
                minLen += vec[i].weigth;//统计生成树边的权值
                edge++;
                if (edge == N - 1) {
                    printf("%d\n", minLen);
                    break;
                }
            }
        }
    }
    return 0;
}