洛谷P2121 最大生成树

最新推荐文章于 2024-08-03 15:53:55 发布

animalcoder

最新推荐文章于 2024-08-03 15:53:55 发布

阅读量284

点赞数

CC 4.0 BY-SA版权

分类专栏： ACM--生成树文章标签：最大生成树

本文链接：https://blog.csdn.net/animalcoder/article/details/100009596

ACM--生成树专栏收录该内容

0 篇文章

订阅专栏

//P2121 1e5带边权 ，选K条不成环的边，使得边权和最大
//最大生成树的过程中选前K条即可
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct edg{
    int u,v,w;
}mp[100005];

int fa[100005];

int find(int x){
    if(x==fa[x])return fa[x];
    return fa[x]=find(fa[x]);
}
int uni(int x,int y){
    x=find(x),y=find(y);
    if(x!=y)fa[x]=y;
}

int main(){
   int n,m,k;cin>>n>>m>>k;
   for(int i=1;i<=n;i++)fa[i]=i;
   for(int i=1;i<=m;i++){
       int u,v,w;cin>>u>>v>>w;
        mp[i].u=u;mp[i].v=v;mp[i].w=w;
   }
   int ans=0;int cnt=0;
   sort(mp+1,mp+1+m,[](edg a,edg b){return a.w>b.w;});
   for(int i=1;i<=m&&cnt<k;i++){
       if(find(mp[i].u)!=find(mp[i].v)){
           uni(mp[i].u,mp[i].v);
           ans+=mp[i].w;cnt++;
       }
   }
   cout<<ans<<endl;
}