zoj1203Swordfish（最小生成树）

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
struct node
{
	int start;
	int end;
	double dis;
}t[10010];
int cmp(node a,node b)
{
	return a.dis<b.dis;
}
int per[5500];
int find(int x)
{
	int r=x;
	while(r!=per[r])
	r=per[r];
	return r;
}
int join(int x,int y)
{
	int fx=find(x);
	int fy=find(y);
	if(fx!=fy)
	{
		per[fx]=fy;
		return 1;
	}
	return 0;
}
int main()
{
	int flag=1;
	int m,n,i,j;
	double x[110],y[110];
	while(scanf("%d",&n),n)
	{
		for(i=0;i<5500;i++)
		per[i]=i;
		for(i=0;i<n;i++)
		scanf("%lf%lf",&x[i],&y[i]);
		int k=0;
		for(i=0;i<n;i++)
		for(j=i+1;j<n;j++)
		{
			t[k].start=i;
			t[k].end =j;
			t[k].dis =sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
			k++;
		}
		sort(t,t+k,cmp);
		double sum=0;
		for(i=0;i<k;i++)
		if(join(t[i].start,t[i].end))
		sum=sum+t[i].dis;
		if(flag!=1)
		printf("\n");
		printf("Case #%d:\n",flag);
		printf("The minimal distance is: ");
		printf("%.2lf\n",sum); 
		flag++;
	}
	return 0;
}

版权声明：本文为博主原创文章，未经博主允许不得转载。