poj-2031

C - Building a Space Station

 题意：在一个三维空间里建造球形的小室，若小室相邻或部分重叠，或者间接有走廊间接相连，则两个小室相连通，给出ｎ个小室，下面ｎ行每行分别是ｎ个小室的球形空间坐标，和球形小室的半径长度。找出让所有球形小室联通所需要建造长廊的最短距离。

思路：相邻两球的距离用球心坐标，和两个球心半径比较。二维数组邻接矩阵存图，两个小室之间所需要长廊的距离为两点之间的权值，若相邻，或重叠，权值为０，最小生成树，找出最短路径。

反思：struct 里x,y,ｚ都要是double型，ｍinn存ｄis数组，也是double型

//

// Created by xrm on 18-11-2.

//

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

using namespace std;

const int maxn=105;

const int inf=0x3f3f3f3f;

double Graph[maxn][maxn];

double dis[maxn];

bool vis[maxn];

struct node{

    double x,y,z,r;

}p[maxn];

int N;

double length(node a,node b){

    double l;

    l=(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z);

    l=sqrt(l);

    if(l-a.r-b.r<0)

        return 0;

    else{

        return l-a.r-b.r;

    }

}

double prim(){

    double ans=0;

    for(int i=0;i<N;i++){

        dis[i]=Graph[0][i];

    }

    dis[0]=0;

    vis[0]=1;

    for(int i=1;i<N;i++){

        int pos=-1;

        double minn=inf;

        for(int j=0;j<N;j++){

            if(!vis[j]&&dis[j]<minn){

                minn=dis[j];

                pos=j;

            }

        }

        vis[pos]=1;

        ans+=minn;

        for(int k=0;k<N;k++){

            if(!vis[k]&&dis[k]>Graph[pos][k]){

                dis[k]=Graph[pos][k];

            }

        }

    }

    return ans;

}

int main(){

    while(cin>>N&&N){

    double sum;

    for(int i=0;i<N;i++){

       scanf("%lf%lf%lf%lf",&p[i].x,&p[i].y,&p[i].z,&p[i].r);

    }

    for(int i=0;i<N;i++){

        for(int j=0;j<N;j++){

            if(i==j)

                Graph[i][j]=0;

            else

                Graph[i][j]=inf;

        }

    }

    for(int i=0;i<N;i++){

        for(int j=i+1;j<N;j++){

           sum=length(p[i],p[j]);

            if(Graph[i][j]>sum)

            Graph[i][j]=Graph[j][i]=sum;

        }

    }

    memset(vis,0,sizeof(vis));

    double dd;

    dd=prim();

    printf("%.3f\n",dd);

    }

    return 0;

}