题目链接：
POJ 2031 Building a Space Station
题意：
给定一些球的圆心与半径，如果两个球之间相交，则他们之间连通，
否则不连通，问还需要连多长的边使所有球都连通
分析：任意两个球，如果连通则边权为0，
否则边权为d-r1-r2，d是两球圆心坐标之间的距离，r1与r2分别为两个球的半径，
这样求一个最小生成树，将所有球连接起来
注意：
数据double类型的时候，用G++的时候scanf要用%lf,而printf的时候要用%f，否则会WA！
CODE :
//Kruskal Algorithm
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;const int maxn=105;
const double eps=1e-8;int n,tot,uu,vv;
int pre[maxn];
double ans,ww;struct Point{double x,y,z,r;
}point[maxn];struct Edge{int u,v;double w;
}edge[maxn*maxn];void init()
{ans=0;tot=0;for(int i=0;i<maxn;i++)pre[i]=i;
}int find(int x)
{return pre[x]==x?x:pre[x]=find(pre[x]);
}double Distance(struct Point a,struct Point b)
{double dis=0;double xx=a.x-b.x;double yy=a.y-b.y;double zz=a.z-b.z;//double tmp=sqrt(xx*xx+yy*yy+zz*zz)-a.r-b.r;//if(tmp>eps) dis=tmp;dis=max(dis,sqrt(xx*xx+yy*yy+zz*zz)-a.r-b.r);//不用eps精度限制也能ACreturn dis;
}bool cmp(struct Edge a,struct Edge b)
{return a.w<b.w;
}int main()
{
#ifdef LOCALfreopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);
#endifwhile(~scanf("%d",&n)&&n){init();for(int i=1;i<=n;i++)scanf("%lf%lf%lf%lf",&point[i].x,&point[i].y,&point[i].z,&point[i].r);for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){edge[tot].u=i;edge[tot].v=j;edge[tot].w=Distance(point[i],point[j]);tot++;}}sort(edge,edge+tot,cmp);//Kruskal Algorithmfor(int i=0;i<tot;i++){uu=edge[i].u;vv=edge[i].v;ww=edge[i].w;int fu=find(uu);int fv=find(vv);if(fu!=fv){pre[fu]=fv;ans+=ww;}}printf("%.3f\n",ans);}return 0;
}
//Prim Algorithm
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;const int maxn=105;
const double eps=1e-8;
const int INF=0x3f3f3f3f;int n,s,vis[maxn],k;
double ans,map[maxn][maxn],dis[maxn];
double mindis;struct Point{double x,y,z,r;
}point[maxn];double Distance(struct Point a,struct Point b)
{double dis=0;double xx=a.x-b.x;double yy=a.y-b.y;double zz=a.z-b.z;//double tmp=sqrt(xx*xx+yy*yy+zz*zz)-a.r-b.r;//if(tmp>eps) dis=tmp;dis=max(dis,sqrt(xx*xx+yy*yy+zz*zz)-a.r-b.r);//不用eps精度限制也能ACreturn dis;
}int main()
{
#ifdef LOCALfreopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);
#endifwhile(~scanf("%d",&n)&&n){for(int i=1;i<=n;i++)scanf("%lf%lf%lf%lf",&point[i].x,&point[i].y,&point[i].z,&point[i].r);for(int i=1;i<=n;i++){map[i][i]=0;for(int j=i+1;j<=n;j++){map[i][j]=map[j][i]=Distance(point[i],point[j]);}}ans=0;memset(vis,0,sizeof(vis));s=1;vis[s]=1;//记录开始点for(int i=1;i<=n;i++)dis[i]=map[s][i];for(int i=1;i<n;i++)//运行n-1次，每次添加一个顶点{mindis=INF;k=-1;for(int j=1;j<=n;j++)//从未连通点中找到权值最小的点{if(!vis[j]&&dis[j]<mindis){mindis=dis[j];k=j;}}vis[k]=1;//标记已连通ans+=mindis;//权值累加for(int j=1;j<=n;j++)//更新权值{if(!vis[j]&&dis[j]>map[k][j])dis[j]=map[k][j];}}printf("%.3f\n",ans);}return 0;
}
