题意：
给出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; }