poj 2031

裸prim，就是算距离麻烦了点。。。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#define MAX 150
#define INF 0x3f3f3f3f
using namespace std;

struct Node {
  double x, y, z, r;
} point[MAX];

double map[MAX][MAX];
int visit[MAX];
double low[MAX];
int n;
double prim() {
  double sum = 0;
  visit[0] = 1;
  for (size_t i = 0; i < n; i++) {
    {
      if (!visit[i]) {
        low[i] = map[i][0];
      }
    }
  }

  for (size_t i = 0; i < n - 1; i++) {
    {

      double minn = (double)INF;
      int u;
      for (size_t j = 0; j < n; j++) {
        if (!visit[j] && low[j] < minn) {
          minn = low[j];
          u = j;
        }
      }
      visit[u] = 1;
      sum += minn;

      for (size_t j = 0; j < n; j++) {
        if (!visit[j] && low[j] > map[u][j])
          low[j] = map[u][j];
      }
    }
    /* code */
  }
  return sum;
}

int main() {
  while (~scanf("%d", &n)) {
    if (n == 0)
      break;
    memset(visit, 0, sizeof(visit));
    double x, y, z, r;
    for (int i = 0; i < n; i++) {
      scanf("%lf%lf%lf%lf", &x, &y, &z, &r);
      point[i].x = x;
      point[i].y = y;
      point[i].z = z;
      point[i].r = r;
    }

    for (size_t i = 0; i < n; i++) {
      for (size_t j = i + 1; j < n; j++) {

        double ddis = pow(fabs(point[i].x - point[j].x), 2) +
                      pow(fabs(point[i].y - point[j].y), 2) +
                      pow(fabs(point[i].z - point[j].z), 2);
        double dis = sqrt(ddis);
        if (dis <= (point[i].r + point[j].r)) {
          map[i][j] = map[j][i] = 0;

        } else
          map[i][j] = map[j][i] = dis - point[i].r - point[j].r;
      }
    }
    printf("%.3lf\n", prim());
  }

  return 0;
}