AcWing 859. Kruskal算法求最小生成树
原题链接
简单
作者:
术
,
2021-01-24 20:50:09
,
所有人可见
,
阅读 318
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=100005;
int n,m;
int p[N];
struct Edge{
int a,b,w;
bool operator<(const Edge &W)const{
return w<W.w;
}
}edges[N*2];
int find(int x){
if(x!=p[x]) return p[x]=find(p[x]);
return p[x];
}
int main()
{
cin>>n>>m;
for(int i=0;i<m;i++){
int a,b,c;
cin>>a>>b>>c;
edges[i].a=a,edges[i].b=b,edges[i].w=c;
}
for(int i=1;i<=n;i++)
p[i]=i;
sort(edges,edges+m);
int res=0,num=0;
for(int i=0;i<m;i++){
int a=edges[i].a,b=edges[i].b,w=edges[i].w;
//a=find(a),b=find(b);
if(find(a)!=find(b)){
res+=w;
num++;
p[find(a)]=b;
}
}
if(num+1==n)
cout<<res;
else
cout<<"impossible";
//cout << "Hello world!" << endl;
return 0;
}