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

}
巴特西

$P2126 Mzc家中的男家丁$

最新文章

热门文章
