poj 2031 Building a Space Station (最小生成树)

  1/* ***********************************************
  2Author :111qqz
  3Created Time :2016年07月14日 星期四 15时44分53秒
  4File Name :code/poj/2031.cpp
  5 ************************************************ */
  6#include <cstdio>
  7#include <cstring>
  8#include <iostream>
  9#include <algorithm>
 10#include <vector>
 11#include <queue>
 12#include <set>
 13#include <map>
 14#include <string>
 15#include <cmath>
 16#include <cstdlib>
 17#include <ctime>
 18#define fst first
 19#define sec second
 20#define lson l,m,rt<<1
 21#define rson m+1,r,rt<<1|1
 22#define ms(a,x) memset(a,x,sizeof(a))
 23typedef long long LL;
 24#define pi pair < int ,int >
 25#define MP make_pair
 26using namespace std;
 27const double eps = 1E-8;
 28const int dx4[4]={1,0,0,-1};
 29const int dy4[4]={0,-1,1,0};
 30const int inf = 0x3f3f3f3f;
 31const  int N =105;
 32int n;
 33int m; 
 34double a[N][N];
 35int f[N];
 36int dblcmp(double d)
 37{
 38    return d<-eps?-1:d>eps;
 39}
 40void init()
 41{
 42    for ( int i = 1 ; i  <= n ; i++) f[i] = i;
 43}
 44struct circle
 45{
 46    double x,y,z,r;
 47    double dis(circle b)
 48    {
 49	double res = 0 ;
 50	res = (x-b.x)*(x-b.x)+(y-b.y)*(y-b.y)+(z-b.z)*(z-b.z);
 51	res = sqrt(res);
 52	res = res - r - b.r;
 53	if (dblcmp(res)<0) res = 0 ;
 54	return res;
 55    }
 56    void input()
 57    {
 58	scanf("%lf%lf%lf%lf",&x,&y,&z,&r);
 59    }
 60}cir[N];
 61struct Edge
 62{
 63    int u,v;
 64    double w;
 65    bool operator < (Edge b)const
 66    {
 67	return w<b.w;
 68    }
 69}edge[N*N/2];
 70int root ( int x)
 71{
 72    if (x!=f[x]) f[x] = root (f[x]);
 73    return f[x];
 74}
 75void merge( int x,int y)
 76{
 77    int rx = root (x);
 78    int ry = root(y);
 79    if (rx==ry) return;
 80    f[rx] = ry;
 81}
 82int main()
 83{
 84#ifndef  ONLINE_JUDGE 
 85    freopen("code/in.txt","r",stdin);
 86#endif
 87    while (~scanf("%d",&n))
 88    {
 89	if (n==0) break;
 90	init();
 91	for ( int i = 1 ;i  <= n ; i++) cir[i].input();
 92	for ( int i = 1 ; i <= n ; i++)
 93	    for ( int j = 1 ; j <= n ; j++)
 94		a[i][j]=a[j][i]=cir[i].dis(cir[j]);
 95	m = 0 ;
 96	for ( int i = 1 ; i <= n ; i++)
 97	    for ( int j = 1 ; j <= n ; j++)
 98		if (i<j)
 99		{
100		    m++;
101		    edge[m].u = i ;
102		    edge[m].v = j;
103		    edge[m].w = a[i][j];
104		}
105	sort(edge+1,edge+m+1);
106	double mst = 0 ;
107	int cnt = 0 ;
108	for ( int i = 1 ; i <= m ; i++)
109	{
110	    int u = edge[i].u;
111	    int v = edge[i].v;
112	    double w = edge[i].w;
113	    if (root(u)==root(v)) continue;
114	    merge(u,v);
115	    mst +=w;
116	    cnt++;
117	    if (cnt>=n-1) break;
118	}
119	if (dblcmp(mst)==0)
120	{
121	    puts("0.000");
122	}else
123	{
124	    printf("%.3f\n",mst);
125	}
126    }
127#ifndef ONLINE_JUDGE  
128    fclose(stdin);
129#endif
130    return 0;
131}