这题目，用G++ WA，用C++ AC。
题目要求，现给出n个球，然后要使每两个球直接或者间接连通，可以在任意两球之间做管道（在表面），最后的要求是，如果使得都连通的话，管道最小长度是多少。
思路简单，就是求出来每两个球之间的距离，球心差减去两球的半径，注意如果这里是负的则处理为0。然后就是克鲁斯卡尔求最小生成树就可以了。
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <algorithm>
#define eps 0.00000001
struct point{
double x,y,z,r;
}p[];
struct edge{
int u,v;
double w;
}e[*];
int parent[];
int n,cnt;
void ufset(){
int i;
for(i=;i<=n;++i) parent[i]=-;
return;
}
int find(int x){
int s;
for(s=x;parent[s]>=;s=parent[s]);
while(s!=x){
int tmp=parent[x];
parent[x]=s;
x=tmp;
}
return s;
}
void Union(int R1,int R2){
int r1=find(R1),r2=find(R2);
int tmp=parent[r1]+parent[r2];
if(parent[r1]>parent[r2]){
parent[r1]=r2; parent[r2]=tmp;
}else{
parent[r2]=r1; parent[r1]=tmp;
}
return;
}
int cmp(struct edge a,struct edge b){
return eps<b.w-a.w;
}
double kruskal(){
double sumweight=;
int i;
int num=;
int u,v;
ufset();
for(i=;i<cnt;++i){
u=e[i].u; v=e[i].v;
if(find(u)!=find(v)){
sumweight+=e[i].w; num++;
// printf("sumweight=%lf,u=%d,v=%d\n",sumweight,u,v);
Union(u,v);
}
if(num>=n-) break;
}
return sumweight;
} double count(struct point a,struct point b){
double res;
res=sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) + (a.z-b.z)*(a.z-b.z) ) - a.r - b.r ;
if( -res > eps ) res=;
return res;
} int main(){
int i,j;
while(~scanf("%d",&n)){
if(n==) break;
for(i=;i<n;++i){
scanf("%lf%lf%lf%lf",&p[i].x,&p[i].y,&p[i].z,&p[i].r);
}
cnt=;
for(i=;i<n;++i){
for(j=;j<i;++j){
e[cnt].u=i;
e[cnt].v=j;
e[cnt].w=count(p[i],p[j]);
cnt++;
}
}
std::sort(e,e+cnt,cmp);
// for(i=0;i<cnt;++i){
// printf("%lf\n",e[i].w);
// }
// printf("------------\n");
double res=kruskal();
printf("%.3lf\n",res);
}
return ;
}
计算几何+克鲁斯卡尔