首页 > 其他 > 详细

Kruskal

时间:2019-05-18 10:55:02      阅读:136      评论:0      收藏:0      [点我收藏+]
/*
    Kruskal
*/
#include <bits/stdc++.h>

using namespace std;

const int N = 200001;
const int M = 500001;

struct Node{
    int u,v;
    int val;
}A[M];

int n,m,p,cnt,cost,fa[N];

bool cmp(Node a, Node b){
    return a.val < b.val;
}

void add(int u, int v, int val){
    A[++p].u = u;
    A[p].v = v;
    A[p].val = val;
}

int find(int x){
    return x == fa[x] ? x : fa[x] = find(fa[x]); 
}

void Kruskal(){
    sort(A + 1, A + m + 1, cmp);
    for(int i = 1; i <= m; ++i){
        int fu = find(A[i].u);
        int fv = find(A[i].v);
        if(fu == fv) continue;
        fa[fu] = fv;
        cost += A[i].val;
        ++cnt;
    }
}
        
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) fa[i] = i;
    for(int i = 1, u, v, val; i <= m; ++i) cin >> u >> v >> val, add(u, v, val);
    Kruskal();
    cnt == n - 1 ? printf("%d", cost) : printf("orz"); 
    return 0;
}

 

Kruskal

原文:https://www.cnblogs.com/Adventurer-H/p/10884496.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!