题目链接
给定N个三维圆心及其半径（x,y,z,r）；求连通它们的最小生成树。两个球若相交视为连通。 N<101，坐标非负且小于100.000。
Input
多组输入，以0结束。
Output
最短连通距离，三位小数。
Sample Input
3
10.000 10.000 50.000 10.000
40.000 10.000 50.000 10.000
40.000 40.000 50.000 10.000
2
30.000 30.000 30.000 20.000
40.000 40.000 40.000 20.000
5
5.729 15.143 3.996 25.837
6.013 14.372 4.818 10.671
80.115 63.292 84.477 15.120
64.095 80.924 70.029 14.881
39.472 85.116 71.369 5.553
0
Sample Output
20.000
0.000
73.834
题意思路：
若2个圆心之间的距离小于等于2个半径之和代表2个圆连通，那么可以认为边权是0.
若不连通边权为 距离-半径之和。
最后求出让所有圆连通的最小的距离（最小生成树）
代码:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=105;
const int inf=0x3f3f3f3f;
struct C
{double x,y,z,r;
} c[maxn];
int n;
double mp[maxn][maxn],dis[maxn];
bool vis[maxn];
double prime()
{double ans=0;for(int i=1;i<=n;i++){dis[i]=inf;}memset(vis,false,sizeof(vis));for(int i=0;i<n;i++)//加入n个点，遍历n次{int v=-1;for(int j=1;j<=n;j++)//Prime算法的核心，遍历所有未加入集合Vnew的点，{if(!vis[j]&&(v==-1||dis[v]>dis[j]))//如果该点未加入Vnew,且该点距离i(u)点较近，则v=j;//更新v点， 直到找到一条距离Vnew中的点u最近的一条边u-v}vis[v]=true;//将v点加入点集合Vnew,相当于将<u,v>边加入边集合Enew中//for(int j=1;j<=n;j++)if(i!=0)//if(i)等价于if(i!=0),if(!i)等价于if(i==0) //在C语言中0为假，非0为真ans+=dis[v];// 不是第一个点的话 加上距离for(int j=1;j<=n;j++){//if(!vis[j]&&dis[j]>mp[v][j])// dis[j]=mp[v][j];// 更新点集合Vnew到其他点的距离 ,直到Vnew=Vdis[j]=min(dis[j],mp[v][j]);}}return ans;
}
int main()
{while(cin>>n&&n!=0){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){mp[i][j]=inf;}}for(int i=1;i<=n;i++){cin>>c[i].x>>c[i].y>>c[i].z>>c[i].r;}for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){double x=c[i].x-c[j].x;double y=c[i].y-c[j].y;double z=c[i].z-c[j].z;double r=c[i].r+c[j].r;double d=sqrt(x*x+y*y+z*z);if(d>r){mp[i][j]=mp[j][i]=min(mp[i][j],d-r);}else{mp[i][j]=mp[j][i]=0;}}}printf("%.3lf\n",prime());//printf输出float和double都可以用%f,double还可以用%lf//scanf输入float用%f,double输入用%lf,不能混用}return 0;
}收获感悟：当你真的理解并熟悉一个算法后，代码行看起来就不是那么难以理解了，当一个相关的算法理解后，还有些看不懂代码时可能就是语法知识点有些还不知道，百度查一下就可以了。然后要做的就是下次再遇到类似的题目时，熟练的把它敲出来。
