loj 123 最小生成树
题解
MST裸题(克鲁斯卡尔裸题, 压缩路径并查集)
#include <bits/stdc++.h> using namespace std; const int maxn = 500010; int fa[maxn]; struct Edge{ int l; int r; int v; bool operator < (const Edge & rhs) const{ return v < rhs.v; } }g[maxn]; int n, m; int find(int x) { int r = x, q; while (r != fa[r]) r = fa[r]; while (x != r) { q = fa[x]; fa[x] = r; x = q; } return r; } void Union(int x, int y){ int fx = find(x), fy = find(y); fa[fx] = fy; } long long MST(){ long long res = 0; for(int i = 0; i < m; ++i){ Edge cur = g[i]; if(find(cur.l) != find(cur.r)) { Union(cur.l, cur.r); res += cur.v; } } return res; } int main() { cin >> n >> m; for(int i = 1; i <= n; ++i) fa[i] = i; for(int i = 0; i < m; ++i){ int a, b, v; cin >> a >> b >> v; g[i] = Edge{a, b, v}; } sort(g, g + m); cout << MST() << endl; return 0; }
博文最后更新时间:
评论
-
暂无评论