学步园

简单最小生成树

#include<stdio.h>
#include<stdlib.h>
#define inf 0x3fffffff
int f[1010],n,map[1010][1010];
struct op
{
	int x,y,w;
}p[10100];
int find(int a)
{
	if(a!=f[a])
		f[a]=find(f[a]);
	return f[a];
}
int cmp(const void *a,const void *b)
{
	struct op *c,*d;
	c=(struct op *)a;
	d=(struct op *)b;
	return c->w-d->w;
}
int main()
{
	int i,j,a,b,c,num,count,sum,m;
	while(scanf("%d%d",&n,&m)!=-1)
	{
		num=0;
		for(i=0;i<n;i++)
		{
			f[i]=i;
			for(j=0;j<n;j++)
				map[i][j]=inf;
		}
			for(i=1;i<=m;i++)
			{
				scanf("%d%d%d",&a,&b,&c);
				if(map[a][b]>c)
				{
					map[a][b]=map[b][a]=c;
				}
			}
			for(i=0;i<n;i++)
				for(j=i+1;j<n;j++)
					if(map[i][j]<inf)
					{
						p[num].x=i;
						p[num].y=j;
						p[num++].w=map[i][j];
					}
					qsort(p,num,sizeof(p[0]),cmp);
					count=0;sum=0;
					for(i=0;i<num;i++)
					{
						if(count==n-1)break;
						a=find(p[i].x);
						b=find(p[i].y);
						if(a==b)continue;
						f[b]=find(f[a]);
						sum+=p[i].w;
					    count++;
					}
					if(count<n-1)
						puts("impossible");
					else printf("%d\n",sum);
					printf("\n");
	}
	return 0;
}