AcWing 859. Kruskal算法求最小生成树
原题链接
简单
作者:
术
,
2021-12-30 20:16:11
,
所有人可见
,
阅读 172
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5+5;
int n, m;
int p[N];
int cnt = 1;
class Edge{
public:
int a, b, w;
bool operator < (const Edge &B){
return this->w < B.w;
}
};
Edge edges[N];
int Find(int x){
if(p[x] != x) p[x] = Find(p[x]);
return p[x];
}
int kruscal(){
int res = 0;
for(int i = 0; i < m; i++){
int a = edges[i].a, b = edges[i].b, w = edges[i].w;
int pa = Find(a), pb = Find(b);
if(pa != pb){
p[pa] = pb;
res += w;
cnt ++;
}
}
return res;
}
int main()
{
cin>>n>>m;
for(int i = 0; i < m; i++){
int a, b, w;
cin>>a>>b>>w;
edges[i] = {a, b, w};
}
sort(edges, edges + m);//对边进行排序
// for(int i = 0; i < m; i++){
// int a, b, w;
// cout<<edges[i].w<<endl;
// }
for(int i = 1; i <= n; i++) p[i] = i;
int res = kruscal();
if(cnt == n)
cout<<res<<endl;
else cout<<"impossible"<<endl;
return 0;
}