题意：
给定一些球的坐标，为这些球搭建通路，使得他们能相互连通，如果两个球有重叠的部分则算为已连通，无需再搭桥，求搭建通路的最小费用，费用就是边权，两个球面的距离。
题解：
最小生成树模板题，两个球起初有重叠，视为已经连通，边权为0。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<string>
#include<cstring>
#include<vector>
#include<functional>
#include<utility>
#include<set>
#include<map>
#include<cmath>
#include<cctype>using namespace std;
const int maxn=105;struct edge
{int u,v;double cost;edge(int u,int v,double d):u(u),v(v),cost(d){}bool operator<(const edge& a)const{return cost<a.cost;}
};
struct point{double x,y,z,r;}a[maxn];vector<edge>es;
int pa[maxn];
int n;
int findset(int x){return pa[x]<0?x:pa[x]=findset(pa[x]);}double kk()
{sort(es.begin(),es.end());memset(pa,-1,sizeof(pa));int cnt=0;double sum=0;for(int i=0;i<es.size();i++){int u=es[i].u, v=es[i].v;if(findset(u)!=findset(v)){pa[findset(u)]=findset(v);sum+=es[i].cost;if(++cnt>=n-1)break;//给的图是连通的，为什么直接return不行？}}return sum;
}double dist(int i,int j)
{double len=sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y)+(a[i].z-a[j].z)*(a[i].z-a[j].z));double ans=len-a[i].r-a[j].r;if(ans<0)return 0;//有重叠return ans;
}int main()
{while(scanf("%d",&n)==1&&n){es.clear();for(int i=0;i<n;i++)cin>>a[i].x>>a[i].y>>a[i].z>>a[i].r;for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)es.push_back(edge(i,j,dist(i,j)));printf("%.3lf\n",kk());}
}
