这个题要交c++， 因为prime的返回值错了，改了一会
题目：http://poj.org/problem?id=2031
题意：就是给出三维坐标系上的一些球的球心坐标和其半径，搭建通路，使得他们能够相互连通。如果两个球有重叠的部分则算为已连通，无需再搭桥。求搭建通路的最小费用（费用就是边权，就是两个球面之间的距离
思路：求球之间的距离， 距离小于半径 说明联通 ， 距离为0.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
double const INF=<<;
double G[][]; struct node
{
double x,y,z,r;
}p[];
double prime(int n)
{
double sum=0.0;
int i,j,pos;
int v[]={};
double d[],min;
for(i=; i<=n; i++)
d[i]=G[][i];
v[]=;
for(i=; i<=n; i++)
{
min=INF;
for(j=; j<=n; j++)
{
if(!v[j]&&min>d[j])
{
min=d[j];
pos=j;
}
}
sum+=min;
v[pos]=;
//printf("%.3lf %.3lf\n",min,sum);
for(j=; j<=n; j++)
{
if(!v[j])
{
if(d[j]>G[pos][j])
d[j]=G[pos][j];
}
}
//printf("%.3lf %.3lf\n",min,sum);
}
//printf("%.3lf\n",sum);
return sum;
}
int main()
{
int n,i,j;
double d,sum;
while(scanf("%d",&n)&&n)
{
memset(p,,sizeof(p));
for(i=; i<=n; i++)
{
for(j=; j<=n; j++)
G[i][j]=INF;
G[i][i]=;
}
for(i=; i<=n; i++)
{
scanf("%lf%lf%lf%lf",&p[i].x,&p[i].y,&p[i].z,&p[i].r);
for(j=; j<i; j++)
{
d=sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y)
+(p[i].z-p[j].z)*(p[i].z-p[j].z));
if(d-p[i].r-p[j].r<=)
G[i][j]=G[j][i]=;
else
G[i][j]=G[j][i]=d-p[i].r-p[j].r;
}
}
sum=prime(n);
printf("%.3lf\n",sum);
}
return ;
}