Building a Space Station

 

题目：http://poj.org/problem?id=2031

空间站之间建立通道， 使得所有空间站连通， 最小生成树问题。 道路长度不会有负权。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int N = 101;double a[N], b[N], c[N], d[N], dis[N], map[N][N]; int vis[N];int n; void Prime(){    double sum = 0.0;    memset(vis, 0, sizeof(vis));    for(int i = 1; i <= n; i++)        dis[i] = map[1][i];    vis[1] = 1;    for(int i = 1; i < n; i++)     {        int temp = 1; double min = 99999;        for(int j = 1; j <= n; j++)        {            if(!vis[j] && dis[j] < min)            {                temp = j;                min = dis[j];              }         }        sum += min;        vis[temp] = 1;        for(int j = 1; j <= n; j++)            if(!vis[j] && dis[j] > map[temp][j])                 dis[j] = map[temp][j];    }    printf("%.3lf\n", sum);}int main(){    while(~scanf("%d", &n), n)    {        for(int i = 1; i <= n; i++)            scanf("%lf%lf%lf%lf", &a[i], &b[i], &c[i], &d[i]);        for(int i = 1; i <= n; i++)            for(int j = 1; j <= n; j++)            {                double TeMp = sqrt((a[i]-a[j])*(a[i]-a[j])+(b[i]-b[j])*(b[i]-b[j])+(c[i]-c[j])*(c[i]-c[j]))-d[i]-d[j];                if(TeMp < 0)                    map[i][j] = 0;                else                    map[i][j] = TeMp;                }            /*    for(int i = 1; i <= n; i++)                for(int j = 1; j <= n; j++)                    printf(j == n? "%.3lf\n":"%.3lf ", map[i][j]);        */    Prime();    }     return 0;}