题意：
给出n个球体的球心坐标和半径，可以在两个球体的表面连一条通路，代价为距离. 求使得所有球体联通的最小花费.
题解：
最小生成树裸板子
暴力把每个球体的表面之间的距离求出（即 dis=球心距 - 半径和）
注意 如果 dis<0 则 dis=0
代码：
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<cstring>
#include<vector>
#define eps 1e-8
using namespace std;
typedef long long ll;
const int maxn = 1e6+5;
int f[maxn];
int cnt,n;
double x[maxn],y[maxn],z[maxn],r[maxn];
struct node
{
int u,v;
double w;
bool operator < (const node &a)const
{
return w<a.w;
}
}edge[maxn];
int sign(double x)
{
if(fabs(x)<eps)return 0;
return x<0?-1:1;
}
int Find(int x)
{
return x==f[x]?x:f[x]=Find(f[x]);
}
double kruskal()
{
double ans=0.0;
for(int i=0; i<=n; i++)f[i]=i;
sort(edge,edge+cnt);
for(int i=0; i<cnt; i++)
{
int x=edge[i].u;
int y=edge[i].v;
int fx=Find(x);
int fy=Find(y);
if(fx!=fy)
{
f[fx]=fy;
ans+=edge[i].w;
}
}
return ans;
}
double get_dis(int i,int j)
{
double dis=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]))-(r[i]+r[j]);
if(dis>=0)return dis;
return 0;
}
int main()
{
while(~scanf("%d",&n) && n)
{
memset(edge,0,sizeof edge);
for(int i=1; i<=n; i++)scanf("%lf%lf%lf%lf",&x[i],&y[i],&z[i],&r[i]);
cnt=0;
for(int i=1; i<=n; i++)
{
for(int j=i+1; j<=n; j++)
{
edge[cnt].u=i;
edge[cnt].v=j;
edge[cnt++].w=get_dis(i,j);
}
}
printf("%.3f\n",kruskal());
}
return 0;
}