Building a Space Station POJ - 2031 （最小生成樹）

題：

您是空間站工程團隊的成員，在空間站的建造過程中被配置設定了一項任務。您需要編寫一個計算機程式來完成該任務。

空間站由許多單元組成，稱為單元。所有的細胞都是球形的，但它們的大小不一定是一緻的。在空間站成功進入軌道後不久，每個單元就固定在預定位置。奇怪的是，兩個細胞可能互相接觸，甚至可能重疊。在極端情況下，一個單元可能完全封閉另一個單元。我不知道這樣的安排是怎麼可能的。

所有的單元都必須連接配接起來，因為機組成員應該能夠從任何一個單元走到任何其他單元。如果（1）A和B彼此接觸或重疊，（2）A和B通過“走廊”連接配接，或者（3）有一個C單元，這樣從A到C以及從B到C都可以從A單元步行到另一個B單元。請注意，條件（3）應進行傳遞性解釋。

您需要設計一個配置，即哪對單元将與走廊連接配接。在走廊配置中有一些自由。例如，如果有三個單元格A、B和C，彼此不接觸或不重疊，則至少可以有三個計劃來連接配接所有三個單元格。第一個是修建A-B和A-C走廊，第二個是B-C和B-A走廊，第三個是C-A和C-B走廊。修建走廊的成本與其長度成正比。是以，應選擇走廊總長度最短的平面圖。

可以忽略走廊的寬度。在兩個單元表面上的點之間建立一條走廊。它可以任意長，但當然要選最短的。即使兩條走廊A-B和C-D在空間上相交，也不認為它們在（例如）A和C之間形成連接配接路徑。換句話說，您可能認為兩條走廊從未相交。

輸入

輸入由多個資料集組成。每個資料集的格式如下。

N号

x1 y1 z1 r1型

x2 Y2 Z2 R2型

……

Xn-yn-zn-rn型

資料集的第一行包含整數n，即單元格數。n為正，不超過100。

以下n行是對單元格的描述。一條直線上的四個值是圓心的x、y和z坐标，以及球體的半徑（問題的其餘部分稱為r），順序如下。每個值都由一個小數點給出，小數點後有3位數字。值由空格字元分隔。

x、y、z和r中的每一個都是正的，小于100.0。

輸入的結尾由包含零的行訓示。

輸出

對于每個資料集，應列印走廊的最短總長度，每一條都單獨列印。列印的值應在小數點後3位。誤差不得大于0.001。

請注意，如果不需要走廊，也就是說，如果所有單元都沒有走廊連接配接，則走廊的最短總長度為0.000。

題解：

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include <iostream>
#include <stack>
using namespace std;
#define MaxInt 0x3f3f3f3f
#define N 110
//建立map二維數組儲存圖表，low數組記錄每2個點間最小權值，visited數組标記某點是否已通路
double map1[N][N],low[N],visited[N];
int n,pos=1;
int w=0;
double prim()
{
    int i,j,pos;
    double min1,result=0;
    memset(visited,0,sizeof(visited));
//從某點開始，分别标記和記錄該點
    visited[1]=1;
    pos=1;
//第一次給low數組指派
    for(i=1; i<=n; i++)
        //if(i!=pos)
        low[i]=map1[pos][i];
//再運作n-1次
    for(i=1; i<n; i++)
    {
//找出最小權值并記錄位置
        min1=MaxInt;
        for(j=1; j<=n; j++)
            if(visited[j]==0&&min1>low[j])
            {
                min1=low[j];
                pos=j;
            }
//最小權值累加
        result+=low[pos];
//标記該點
        visited[pos]=1;
//更新權值
        for(j=1; j<=n; j++)
            if(visited[j]==0&&low[j]>map1[pos][j])
                low[j]=map1[pos][j];
    }
   return result;
}

int main()
{
    double x[909],y[909],z[909],r[909],d=0;
    int i,j,F;
    double ans;
    int t;
    double v[9999],re=0;
    memset(v,0,sizeof(v));
    while(scanf("%d",&n)&&n)
    {
//所有權值初始化為最大
        t=1;
        F=n;
        for(i=1; i<=n; i++)
            for(j=1; j<=n; j++)
            {
                if(i==j)
                    map1[i][j]=0;
                else
                    map1[i][j]=MaxInt;
            }

        //cout<<w<<endl;
         for(i=1; i<=n; i++)
        {
            scanf("%lf%lf%lf%lf",&x[i],&y[i],&z[i],&r[i]);
        }
        for(i=1; i<=n; i++)
        {
            //scanf("%lf%lf%lf%lf",&x[i],&y[i],&z[i],&r[i]);

            //cout<<v[i]<<endl;
            for(j=1+i; j<=n; j++)
            {

                d=(double)sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])+(z[i]-z[j])*(z[i]-z[j]));
                d=d-r[i]-r[j];
                if(d<=0)
                    d=0;
                map1[i][j]=map1[j][i]=d;
            }


        }
         re=prim();
         printf("%.3lf\n",re);

    }
    return 0;
}