$P2126 Mzc家中的男家丁$


problem

#ifdef Dubug

#endif
#include <bits/stdc++.h>
using namespace std;
typedef long long LL ;
inline LL In() { LL res(0),f(1); register char c ;
    while(isspace(c=getchar())) ; c == '-'? f = -1 , c = getchar() : 0 ;
    while(res = (res << 1) + (res << 3) + (c & 15) , isdigit(c=getchar())) ;
    return res * f ;
}

int n , m ;
const int N = 2300 + 5 ;
const int M = 400000 + 5 ;
struct node {
    int u ;
    int v ;
    int w ;
};
node edge[M] ;
int fa[N] ;
int ans = 0 ;
bool cmp(node x,node y) {
    return x.w < y.w ;
}
inline int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]) ;
}
inline void kruskal() {
    sort(edge+1,edge+m+1,cmp) ;
    for(register int i=1;i<=m;i++){
        int x = find(edge[i].u) , y = find(edge[i].v) ;
        if(x == y) continue ;
        fa[x] = y , ans += edge[i].w ;
    }
}
signed main() {
    n = In() ; m = In() ;
    for(register int i=1;i<=n;i++) fa[i] = i ;
    for(register int i=1;i<=m;i++) {
        int u = In() , v = In() , w = In() ;
        edge[i] = node{u,v,w} ;
    }
    kruskal() ;
    cout << ans << endl ;
    return 0 ;
}
优质内容筛选与推荐>>
1、vim基本命令
2、tomcat配置问题
3、STL源码剖析——序列式容器#4 Stack & Queue
4、浪潮面试
5、创建XNA Shooter游戏——概述


长按二维码向我转账

受苹果公司新规定影响,微信 iOS 版的赞赏功能被关闭,可通过二维码转账支持公众号。

    阅读
    好看
    已推荐到看一看
    你的朋友可以在“发现”-“看一看”看到你认为好看的文章。
    已取消,“好看”想法已同步删除
    已推荐到看一看 和朋友分享想法
    最多200字,当前共 发送

    已发送

    朋友将在看一看看到

    确定
    分享你的想法...
    取消

    分享想法到看一看

    确定
    最多200字,当前共

    发送中

    网络异常,请稍后重试

    微信扫一扫
    关注该公众号