万能浏览器手机版_网络代理在哪_精准引流客源的方法可靠吗_厦门网站seo

题目：Kruskal算法求最小生成树

 

分析

贪心，每次选最小的边同时两个点不属于同一连通分量即可。

代码

#include<bits/stdc++.h>
using namespace std;const int N = 1e5+10;
int n, m;int p[N];
struct E {int a, b, w;bool operator < (const E &W) const {return w < W.w;}
}edg[N*2];void initP(int x) {for(int i = 1; i <= n; i ++) {p[i] = i;}
}int find(int x) {if(x!=p[x]) p[x] = find(p[x]);return p[x];
}void Kruskal() {int res = 0, cnt = 0;for(int i = 1; i <= m; i ++) {int pa = find(edg[i].a), pb = find(edg[i].b);if(pa != pb) {res += edg[i].w;p[pa] = pb, cnt ++;}}if(cnt == n-1) cout << res << endl;else cout << "impossible" << endl;
}int main() {cin >> n >> m;initP(n);for(int i = 1; i <= m; i ++) {int a, b, w;cin >> a >> b >> w;edg[i] = {a,b,w};}sort(edg+1,edg+1+m);Kruskal();return 0;
}