Closer's Space

梦河之上, 一叶扁舟

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;
}

博文最后更新时间:


评论

  • 暂无评论

发表评论

来访统计

访问量:79

评论总数:0