[Aha]镖局运镖

镖局运镖"/>

[Aha]镖局运镖

题目：详见啊哈算法P212页。
分析：最小生成树-需要结合并查集。
代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std ;int f[1000];
class edge{public:int u ; int v ; int w ; 
};int getf(int x){if(x==f[x]) return x ; else return f[x] = getf(f[x]);
}int merge(int a ,int b){int tx = getf(a);int ty = getf(b);if(tx!=ty){f[ty] = tx ;return 1;} else return 0 ;
}bool compar(edge a , edge b){if(a.w>b.w) return false ; else return true ;
}int main(){freopen("in.txt","r",stdin);int n , m  ,sum ; edge a[1000];while(scanf("%d %d",&n,&m)!=EOF){//初始化 for(int i = 1; i <= n ; i++) f[i] = i ;sum = 0 ; for(int i = 1; i <= m ; i++ ) scanf("%d %d %d",&a[i].u,&a[i].v,&a[i].w);sort(a+1,a+1+m,compar);//for(int i = 1 ; i <= m ; i++) printf("%d %d %d\n",a[i].u,a[i].v,a[i].w);for(int i = 1 ; i <= m ; i++){if(merge(a[i].u,a[i].v)) sum += a[i].w;if(sum == n-1) break ;}printf("%d\n",sum);}return 0 ; 
}