大致題意：
就是給出三維坐標系上的一些球的球心坐標和其半徑，搭建通路，使得他們能夠相互連通。如果兩個球有重疊的部分則算為已連通，無需再搭橋。求搭建通路的最小費用（費用就是邊權，就是兩個球面之間的距離）。
[cpp] #include<iostream>
#include<cmath>
using namespace std;
int vis[105],n;
double map[105][105],l;
double dis(double x1,double y1,double z1,double x2,double y2,double z2)
{
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2));
}
int main()
{
double x[105],y[105],z[105],r[105],d;
int i,j,min,s;
while(scanf("%d",&n)==1 && n)
{
l=0.0;
memset(vis,0,sizeof(vis));
for(i=0;i<n;i++)
{
cin>>x[i]>>y[i]>>z[i]>>r[i];
}
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
d=dis(x[i],y[i],z[i],x[j],y[j],z[j]);
if(d>r[i]+r[j]) map[i][j]=map[j][i]=d-r[i]-r[j];
else map[i][j]=map[j][i]=0;
}
}
vis[0]=1;
for(i=1;i<n;i++)
{
min=-1;
for(j=1;j<n;j++)
{
if(!vis[j])
{
if(min==-1 || map[0][min]>map[0][j]) min=j;
}
}
l+=map[0][min];
vis[min]=1;
for(j=1;j<n;j++)
{
if(!vis[j])
{
if(map[0][j]>map[min][j]) map[0][j]=map[min][j];
}
}
}
printf("%.3lf\n",l);
}
return 0;
}
#include<iostream>
#include<cmath>
using namespace std;
int vis[105],n;
double map[105][105],l;
double dis(double x1,double y1,double z1,double x2,double y2,double z2)
{
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2));
}
int main()
{
double x[105],y[105],z[105],r[105],d;
int i,j,min,s;
while(scanf("%d",&n)==1 && n)
{
l=0.0;
memset(vis,0,sizeof(vis));
for(i=0;i<n;i++)
{
cin>>x[i]>>y[i]>>z[i]>>r[i];
}
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
d=dis(x[i],y[i],z[i],x[j],y[j],z[j]);
if(d>r[i]+r[j]) map[i][j]=map[j][i]=d-r[i]-r[j];
else map[i][j]=map[j][i]=0;
}
}
vis[0]=1;
for(i=1;i<n;i++)
{
min=-1;
for(j=1;j<n;j++)
{
if(!vis[j])
{
if(min==-1 || map[0][min]>map[0][j]) min=j;
}
}
l+=map[0][min];
vis[min]=1;
for(j=1;j<n;j++)
{
if(!vis[j])
{
if(map[0][j]>map[min][j]) map[0][j]=map[min][j];
}
}
}
printf("%.3lf\n",l);
}
return 0;
}
