题目：详见啊哈算法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 ; }