学步园

这题很简单，调用Prim算法（使用了并查集）求最小生成树即可。

我的解题代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <string>
#include <algorithm>

using namespace std;

double x[100],y[100];
double dis[100][100];
int p[100];
int Next[100];
int find(int i)
{
	return (p[i]==i ? i : p[i]=find(p[i]));
}
double Prim(int n)
{
	if(n==1) return 0;
	double totaldis=0;
	for(int i=0; i<n; i++) p[i]=i;
	memset(Next,-1,sizeof(Next));
	int s=0;
	int mini,minj,a,b,mina,minb;
	double mindis;
	for(int k=0; k<n-1; k++)
	{
		mini=s; 
		mina=find(mini);
		for(int i=0; i<n; i++) if(find(i)!=mina) { minj=i; break;}
		minb=find(minj);
		mindis=dis[mini][minj];
		for(int i=s; i!=-1; i=Next[i])
		{
			a=find(i);
			for(int j=0; j<n; j++)
			{
				b=find(j);
				if(a!=b && mindis>dis[i][j]) 
				{
					mindis=dis[i][j];
					mini=i; minj=j;
					mina=a; minb=b;
				}
			}
		}
		p[minb]=mina;
		Next[minj]=Next[s];
		Next[s]=minj;
		totaldis+=mindis;
	}
	return totaldis;
}

int main()
{
	int T,N;
	double tmp;

	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&N);
		for(int i=0; i<N; i++)
		{
			scanf("%lf %lf",&x[i],&y[i]);
			for(int j=0; j<i; j++)
				dis[i][j]=dis[j][i]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
		}
		printf("%.2lf\n",Prim(N));
		if(T) printf("\n");
	}
	return 0;
}