poj 2031 Building a Space Station(prim)(基础) - c++编程基础

给出三维坐标系上的一些球的球心坐标和其半径，搭建通路，使得他们能够相互连通。如果两个球有重叠的部分则算为已连通，无需再搭桥。求搭建通路的最小费用（费用就是边权，就是两个球面之间的距离）。

代码：

//248K	0MS
#include
  
   
#include
   
     #include
    
      #include
     
       using namespace std; #define inf 0xfffffff typedef struct node { double x,y,z; double r; }node; node p[105]; double Map[105][105],dis[105]; int vis[105]; int n; //两个细胞球心间的距离 double dist(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)); } void prim() { for(int i=1;i<=n;i++) { vis[i]=0; dis[i]=Map[1][i]; } vis[1]=1; double Min;int pos; for(int i=1;i<=n;i++) { Min=inf; for(int j=1;j<=n;j++) { if(!vis[j]&&dis[j]
      
       Map[pos][j]) dis[j]=Map[pos][j]; } } double sum=0.0; for(int i=1;i<=n;i++) sum+=dis[i]; printf(%.3lf ,sum); } int main() { double a,b,c; while(scanf(%d,&n),n) { for(int i=1;i<=n;i++) { scanf(%lf%lf%lf%lf,&p[i].x,&p[i].y,&p[i].z,&p[i].r); } double tmp; for(int i=1;i<=n;i++) for(int j=1+i;j<=n;j++) { tmp=dist(p[i],p[j]); if(tmp>(p[i].r+p[j].r)) Map[i][j]=Map[j][i]=tmp-p[i].r-p[j].r; else Map[i][j]=Map[j][i]=0; } prim(); } return 0; }

poj 2031 Building a Space Station(prim)(基础)(二)