只是坐标变成三维得了,而且要减去两边的半径而已
//最小生成树,只是变成三维的了 #define _CRT_SECURE_NO_WARNINGS #include<stdlib.h> #include<stdio.h> #include<iostream> #include<string.h> #include<algorithm> #include<math.h> using namespace std; #define inf 999999999 #define M 110 double mat[M][M]; struct tt { double x,y,z,r; }d[M]; double prim(int n,int sta) { int mark[M],i,j; double dis[M],sum=0; for(i=0;i<n;i++) { dis[i]=mat[sta][i]; mark[i]=0; } mark[sta]=1; for(i=1;i<n;i++) { double minn=inf*1.0; int flag=-1; for(j=0;j<n;j++) { if(mark[j]==0&&dis[j]<minn) { minn=dis[j]; flag=j; } } if(flag!=-1) { mark[flag]=1; sum=sum+dis[flag]; for(j=0;j<n;j++) { if(dis[j]>mat[flag][j]) dis[j]=mat[flag][j]; } } } return sum; } int main() { int i,j,n; double aa; while(scanf("%d",&n),n) { for(i=0;i<n;i++) { scanf("%lf%lf%lf%lf",&d[i].x,&d[i].y,&d[i].z,&d[i].r); for(j=0;j<i;j++) { aa=sqrt((d[i].x-d[j].x)*(d[i].x-d[j].x)+(d[i].y-d[j].y)*(d[i].y-d[j].y)+(d[i].z-d[j].z)*(d[i].z-d[j].z))-d[i].r-d[j].r; aa=aa>0? aa:0; mat[i][j]=mat[j][i]=aa; } } printf("%.3lf\n",prim(n,0)); } return 0; }