3 5 1 2 1 1 3 2 2 3 4 2 3 5 1 3 1
2
#include <cstdio> #include <cstdlib> #include <iostream> #include <cstring> const int N = 50001; const int INF = 200001; using namespace std; struct node{ int u,w,v; }edge[INF]; int father[N],n,m,ans; int cmp(const void *a,const void *b) { node *X,*Y; X = (struct node *)a; Y = (struct node *)b; return X->w - Y->w ; } int find(int r) { int i=r,j; while(father[r]!=r) { r = father[r]; } while(father[i]!=r) { j = father[i]; father[i] = r; i = j; } return r; } void init() { for(int i = 1; i <= n; i++) father[i] = i; } void kruskal() { init(); for(int i = 0; i < m; i++) { int uu = find(edge[i].u); int vv = find(edge[i].v); if(uu != vv) { father[uu] = vv; ans += edge[i].w; } } printf("%d\n",ans); } int main() { while(~scanf("%d%d",&n,&m)) { ans = 0; for(int i =0;i<m;i++) scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w); qsort(edge,m,sizeof(edge[0]),cmp); kruskal(); } return 0; } /**************************************
Result : Accepted Take Memory : 7704K Take Time : 470MS Submit Time : 2014-06-21 16:44:10 **************************************/
原文:http://blog.csdn.net/wjw0130/article/details/32943611