Prim POJ 2031 Building a Space Station

题目传送门

题意：给出n个三维空间的球体，球体是以圆心坐标+半径来表示的，要求在球面上建桥使所有的球联通，求联通所建桥的最小长度。

分析：若两点距离大于两半径和的长度，那么距离就是两点距离 - 半径和，否则为0，Prim写错了，算法没有完全理解

/************************************************
* Author        :Running_Time
* Created Time  :2015/10/25 12:00:48
* File Name     :POJ_2031.cpp
 ************************************************/

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std;

#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 1e2 + 10;
const int E = N * N;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;

bool vis[N];
double d[N];
int head[N];
int n, m, e;
int dcmp(double x)  {       //三态函数，减少精度问题 
    if (fabs (x) < EPS) return 0; 
    else    return x < 0 ? -1 : 1; 
} 
struct Point    {
    double x, y, z, a;
    Point () {}
    Point (double x, double y, double z, double a) : x (x), y (y), z (z), a (a) {}
    Point operator - (const Point &r) const {       //向量减法 
        return Point (x - r.x, y - r.y, z - r.z, 0); 
    } 
};
typedef Point Vector;       //向量的定义 
Point read_point(void)   {      //点的读入 
    double x, y, z, r; 
    scanf ("%lf%lf%lf%lf", &x, &y, &z, &r); 
    return Point (x, y, z, r); 
} 
double dot(Vector A, Vector B)  {       //向量点积 
    return A.x * B.x + A.y * B.y + A.z * B.z; 
} 
double length(Vector A) {       //向量长度，点积 
    return sqrt (dot (A, A)); 
} 

struct Edge {
    int v, nex;
    double w;
    Edge () {}
    Edge (int v, double w, int nex) : v (v), w (w), nex (nex) {}
    bool operator < (const Edge &r) const   {
        return w > r.w;
    }
}edge[E];

void init(void) {
    memset (head, -1, sizeof (head));
    e = 0;
}

void add_edge(int u, int v, double w)   {
    edge[e] = Edge (v, w, head[u]);
    head[u] = e++;
}

double Prim(int s) {
    memset (vis, false, sizeof (vis));
    for (int i=0; i<n; ++i) d[i] = 1e9;
    priority_queue<Edge> Q;
    for (int i=head[s]; ~i; i=edge[i].nex)  {
        int v = edge[i].v;  double w = edge[i].w;
        if (d[v] > w)   {
            d[v] = w;   Q.push (Edge (v, d[v], 0));
        }
    }
    vis[s] = true;  d[s] = 0;
    double ret = 0;
    while (!Q.empty ()) {
        int u = Q.top ().v; Q.pop ();
        if (vis[u]) continue;
        vis[u] = true;  ret += d[u];
        for (int i=head[u]; ~i; i=edge[i].nex)  {
            int v = edge[i].v;  double w = edge[i].w;
            if (!vis[v] && d[v] > w)   {
                d[v] = w;    Q.push (Edge (v, d[v], 0));
            }
        }
    }
    return ret;
}

Point p[N];
int main(void)    {
    while (scanf ("%d", &n) == 1)   {
        if (!n) break;
        for (int i=0; i<n; ++i) {
            p[i] = read_point ();
        }
        init ();
        for (int i=0; i<n; ++i) {
            for (int j=i+1; j<n; ++j)   {
                double dis = length (p[i] - p[j]);
                double len = p[i].a + p[j].a;
                if (dcmp (dis - len) <= 0)   {
                    add_edge (i, j, 0);
                    add_edge (j, i, 0);
                }
                else    {
                    add_edge (i, j, dis - len);
                    add_edge (j, i, dis - len);
                }
            }
        }
        printf ("%.3f
", Prim (0));
    }

    return 0;
}