#include<stdio.h>
#include<string.h>
#include<math.h>
//c++ AC g++ WA 
int n,i,j,k,mini;
double x[110],y[110],z[110],r[110],t,d[110],g[110][110],min,ans;
bool v[110];

int main()
{
	while (scanf("%d",&n)==1&&n)
	{
		for (i=0;i<n;i++)
		 	scanf("%lf%lf%lf%lf",&x[i],&y[i],&z[i],&r[i]);
		for (i=0;i<n;i++)
		{
			g[i][i]=0.0;
			for (j=i+1;j<n;j++)
			{
				t=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])
						+(z[i]-z[j])*(z[i]-z[j]));
				g[i][j]=t-r[i]-r[j];
				if (g[i][j]<1e-8) g[i][j]=0.0;
				g[j][i]=g[i][j];
			}
		}
		/*
		for (i=0;i<n;i++)
		{
			for (j=0;j<n;j++)
				printf("%.3lf\t",g[i][j]);
			printf("\n");
		}
		*/
		for (i=0;i<n;i++) 
		{
			d[i]=g[0][i];
			v[i]=0;
		}
		v[0]=1;
		for (k=0;k<n-1;k++)
		{
			min=100000000.0;
			mini=-1;
			for (i=1;i<n;i++)
				if (!v[i]&&d[i]<min)
				{
					min=d[i];
					mini=i;
				}
			if (mini==-1) break;
			v[mini]=1;
			for (i=1;i<n;i++)
				if (!v[i]&&g[mini][i]<d[i])
					d[i]=g[mini][i];
		}
		ans=0;
		for (i=0;i<n;i++) 
		{
			ans+=d[i];
		//	printf("%.3lf\t",d[i]);
		}
		//printf("\n");
		printf("%.3lf\n",ans);
	}
}

• 我的也是 高手看看！ (1462) 0712105003 2010-04-11 18:51:05
  • Re:我的也是 高手看看！ (1742) qiuzhenguang 2010-04-24 12:11:36