最小生成树-布布扣-bubuko.com

给定一个无向图，每条边有一个非负权值。求这个图中最小生成树的所有边的权值之和。生成树是指包含图中所有节点的一棵树，而最小生成树则指一棵所有边的权值之和最小的生成树。

输入

第一行包含两个数，n和m，其中n为节点数，m为边数。下面m行，每行三个非负整数a、b和c，a, b<n，表示a和b之间有一条权值为c的边。

输出

输出一个数，表示一棵最小生成树所有边的权值之和。

样例输入 Copy

样例输出 Copy

提示

对于30%的数据，m≤10；
对于50%的数据，m≤1000；
对于100%的数据，m≤100000，c≤2000。

#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
inline int read()
{
    int x=0;char ch=getchar();
    while(ch<‘0‘||ch>‘9‘)ch=getchar();
    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
    return x;
}
const int maxn=1e6+100;
int pre[maxn],n,m;
struct node{
    ll u,v,w;
}a[maxn];
bool cmp(node x,node y){
    return x.w<y.w;
} 
void inint(){
    for(int i=0;i<=n;i++){
        pre[i]=i;
    }
}
int find(int h)//找根？ 
{    
    return pre[h]==h?h:pre[h]=find(pre[h]); 
}
int merge(node n){
    int x=find(n.u);
    int y=find(n.v);
    if(x!=y){
        pre[x]=y;
        return 1;
    }
    return 0;
} 
int main(){
    cin>>n>>m;
    inint();
    for(int i=1;i<=m;i++){
        a[i].u=read();
        a[i].v=read();
        a[i].w=read();
    }
    sort(a+1,a+m+1,cmp);
    ll num=0,ans=0; 
    for(int i=1;i<=m&&num<=n-1;i++)
    {
        if(merge(a[i])==1)
        {
            num++;
            ans+=a[i].w;
        }
    }
    printf("%lld\n",ans);
}

https://www.cnblogs.com/SeanOcean/p/10975694.html#autoid-0-0-0

最小生成树

原文：https://www.cnblogs.com/lipu123/p/13302165.html