/*
最小生成树 + 几何判断
Kruskal 球心之间的距离 - 两个球的半径 < 0 则说明是覆盖的！此时的距离按照0计算
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int f[105];
struct ball{
double x, y, z, r;
};
struct connect{
double dist;
int a, b;
};
connect c[5005];
ball b[105];
bool cmp(connect a, connect b){
return a.dist < b.dist;
}
int n;
int getFather(int x){
return x==f[x] ? x : f[x]=getFather(f[x]);
}
int Union(int a, int b){
int fa=getFather(a), fb=getFather(b);
if(fa!=fb){
f[fa]=fb;
return 1;
}
return 0;
}
int main(){
int i, j;
while(scanf("%d", &n) && n){
for(i=1; i<=n; ++i)
scanf("%lf%lf%lf%lf", &b[i].x, &b[i].y, &b[i].z, &b[i].r);
int cnt=0;
for(i=1; i<n; ++i)
for(j=i+1; j<=n; ++j){
double d = sqrt((b[i].x-b[j].x)*(b[i].x-b[j].x) + (b[i].y-b[j].y)*(b[i].y-b[j].y) + (b[i].z-b[j].z)*(b[i].z-b[j].z))
- (b[i].r + b[j].r);
c[cnt].dist= d<0 ? 0: d;
c[cnt].a=i;
c[cnt++].b=j;
}
sort(c, c+cnt, cmp);
double minSum=0.0;
for(i=1; i<=n; ++i)
f[i]=i;
for(i=0; i<cnt; ++i){
if(Union(c[i].a, c[i].b))
minSum+=c[i].dist;
}
printf("%.3lf\n", minSum);
}
return 0;
}
本文转自 小眼儿 博客园博客，原文链接：http://www.cnblogs.com/hujunzheng/p/3877502.html，如需转载请自行联系原作者
![[UVA1364 | POJ | NC]Knights of the Round Table | Tarjan 求点双 | 二分图 | 综合图论](https://ucc.alicdn.com/pic/developer-ecology/d14f6beadb884a3cb2d6c8a10981c6cd.png?x-oss-process=image/resize,h_160,m_lfit)