简单最小生成树 注意建图
#include <iostream> #include <cstring> #include <cmath> #define inf 100000000 #define eps 1e-8 using namespace std; int n; double map[150][150],lowc[150]; bool vis[150]; struct node { double x,y,z,r; }cell[150]; double dis(node a,node b) { return 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)); } double prim() { int i,j,p; double minc,res=0; memset(vis,0,sizeof(vis)); vis[0]=1; for(i=1;i<n;i++) lowc[i]=map[0][i]; for(i=1;i<n;i++) { minc=inf; p=-1; for(j=0;j<n;j++) if(vis[j]==0 && minc>lowc[j]) { minc=lowc[j]; p=j; } if(inf==minc) return -1; res+=minc; vis[p]=1; for(j=0;j<n;j++) if(vis[j]==0 && lowc[j]>map[p][j]) lowc[j]=map[p][j]; } return res; } int main() { int i,j; double d; while(scanf("%d",&n)!=EOF && n) { for(i=0;i<n;i++) scanf("%lf%lf%lf%lf",&cell[i].x,&cell[i].y,&cell[i].z,&cell[i].r); for(i=0;i<n;i++) for(j=0;j<n;j++) { d=dis(cell[i],cell[j]); if(d-cell[i].r-cell[j].r>eps) map[i][j]=d-cell[i].r-cell[j].r; else map[i][j]=0; } printf("%.3lf/n",prim()); } return 0; }