Poj2031--Building a Space Station(Prim )

Building a Space Station

 

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

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

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
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
", 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
":"%.3lf ", map[i][j]);
        */    Prime();
    } 
    return 0;
}