克鲁斯卡尔-并查集-最小生成树算法| #还是畅通工程#

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

const int N = 100+10;

int f[N] = {0};

int find(int n) {
    if (n == f[n])
        return n;
    return find(f[n]);
}

void merge(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra != rb) {
        f[rb] = f[ra];
    }
}

bool isConnect(int a, int b) {
    return find(a) == find(b);
}

void init(int n) {
    //并查集初始化
    for (int i = 0; i <= n; i++)
        f[i] = i;
}

//n个顶点的无向图，联通的最小边数是n-1
int main() {
    int n;
    while (cin >> n) { // 注意 while 处理多个 case
        if(n==0) break ;
        init(n);
        int m = (n * (n - 1)) / 2,cnt=0,p=0,sum=0;
        vector<vector<int>> e(m,vector<int>(3,0)); 
        for (int i = 0; i < m; i++) {
            cin>>e[i][0]>>e[i][1]>>e[i][2];
        }
        //按照公路长度排序
        sort(e.begin(),e.end(),[](auto a,auto b){
            return a[2]<b[2];
        });
        //for_each(e.begin(),e.end(),[](auto x){cout<<x[2]<<endl;});
        //克鲁斯卡尔最小生成树算法，选择n-1条最短的边且不构成回路
        while(cnt<n-1){
            //p初始指向最短的边
            if(!isConnect(e[p][0],e[p][1])){
                //没有联通,可以选择
                sum+=e[p][2];
                //合并，即联通
                merge(e[p][0],e[p][1]);
                cnt++;   
            }
            p++;
        }
        cout<<sum<<endl;
    }
}
// 64 位输出请用 printf("%lld")