最小生成树板子题

直接上kruskal即可

#include <bits/stdc++.h>
using namespace std;

int n,m,cnt = 0;
struct gra{
    int x,y,edge;
}G[500005];
int fa[100005];
bool comp(gra a,gra b){
    return a.edge < b.edge;
}
int find(int x){    //寻找父节点
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void Merge(int x,int y){    //合并操作
    fa[find(x)] = find(y);
}
int Kruskal(){
    int ans = 0,num = 0;
    for(int i = 1;i <= m;i++){
        if(find(G[i].x) != find(G[i].y)){
            ans += G[i].edge;
            Merge(G[i].x,G[i].y);
            //num++;
            //if(num == n-1) break;
        }
    }
    return ans;
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    cin>>n>>m;
    for(int i = 1;i <= m;i++) cin>>G[++cnt].x>>G[cnt].y>>G[cnt].edge;
    sort(G+1,G+1+m,comp);    //按边升序排序
    for(int i = 1;i <= n;i++)    //初始化并查集
        fa[i] = i;        
    cout<<Kruskal();
    return 0;
}