hdu1233 还是畅通工程 （ 最小生成树）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1233

//hdu1233 简单的最小生成树

//代码：

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;
const int maxn=100;
int f[maxn];
struct node
{
	int s,e,len;
} map[10000];

void make()
{
	int i;
	for(i=0;i<maxn;i++)
		f[i]=i;
}

int find(int x)
{
	while(f[x]!=x)
		x=f[x];
	return f[x];
}

void Union(int x,int y)
{
	f[x]=y;
} 
int cmp(const void *a,const void *b)
{
	struct node *c=(node*)a;
	struct node *d=(node*)b;
	return c->len-d->len;
}
int main()
{
	int n;
	while(scanf("%d",&n),n)
	{
		int i;
		for(i=0;i<n*(n-1)/2;i++)
			scanf("%d%d%d",&map[i].s,&map[i].e,&map[i].len);
		make();
		qsort(map,n*(n-1)/2,sizeof(map[0]),cmp);
		int sum=0;
		for(i=0;i<n*(n-1)/2;i++)
		{
			int px=find(map[i].s),
				py=find(map[i].e);
			if(px!=py)
			{
				Union(px,py);
				sum+=map[i].len;
			}
		}
		printf("%d\n",sum);
	}
	return 0;
}