AcWing 859. Kruskal算法求最小生成树
原题链接
简单
作者:
a_little
,
2024-04-12 22:18:37
,
所有人可见
,
阅读 3
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2*1e5+10;
struct Edge{
int a,b,w;
}edge[N];
int p[N];
int find(int x){
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
bool cmp(struct Edge e1,struct Edge e2){
return e1.w<e2.w;
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=0;i<m;i++){
int a,b,w;
cin>>a>>b>>w;
edge[i]={a,b,w};
}
sort(edge,edge+m,cmp);
for(int i=1;i<=n;i++) p[i]=i;
int res=0,cnt=0;
for(int i=0;i<m;i++){
int a,b,w;
a=edge[i].a,b=edge[i].b,w=edge[i].w;
a=find(a);
b=find(b);
if(a!=b){
p[a]=b;
res+=w;
cnt++;
}
}
if(cnt!=n-1) cout<<"impossible";
else cout<<res;
return 0;
}