题解 | #情报#

最小生成树--Kruskal算法

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;

class UnionFind{ // 并查集模板
public:
    vector<int> parent;
    vector<int> rank;

    UnionFind(int n){
        parent.resize(n);
        rank.resize(n);

        for(int i = 0; i < n; ++i){
            parent[i] = i;
            rank[i] = 1;
        }
    }

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


    int find2(int x){
        int ans = x;
        while(ans != parent[ans]){
            ans = parent[ans];
        }
        parent[x] = ans;
        return ans;
    }

    void merge(int x, int y){ // 按秩合并
        int xRoot = find(x);
        int yRoot = find(y);
        if(xRoot != yRoot){
            if(rank[yRoot] <= rank[xRoot]) parent[yRoot] = xRoot;
            else parent[xRoot] = yRoot; // xRoot挂到yRoot上
            if(rank[xRoot] == rank[yRoot]) rank[xRoot]++;
        }
    }
};

void solve(int n, vector<vector<int>>& edges){ // 实现
    ll ans = 0;
    sort(edges.begin(), edges.end(), [&](const auto& x, const auto& y){ // 按边长对边进行排序
        return x[2] < y[2];
    });
    
    UnionFind uf = UnionFind(n); // 并查集
    int count = 0;
    for(auto& ed : edges){ /
        int x = ed[0], y = ed[1];
        if(uf.find(x) != uf.find(y)){ // 合并
            ans += ed[2];
            uf.merge(x, y);
            if(++count == n-1){ // 集合内边的个数为n-1时，结束
                break;
            }
        }
    }
    cout<<ans<<endl;
    return;
}
    
int main(){ // 数据初始化
    int t,n,m;
    cin>>t;
    while(t--){
        cin>>n>>m;
        vector<vector<int>> edges(m+n,vector<int>(3)); 
        int t;
        for(int i = 1; i <= n; ++i){ // val[i] 边长
            cin>>t;
            edges[i-1] = {0,i,t};
        }
        int a,b;
        for(int i = 0; i < m; ++i){ // 记录剩余m条边长
            cin>>edges[n+i][0]>>edges[n+i][1]>>edges[n+i][2];
        }
        solve(n+1,edges);
    }
    return 0;
}