ICPC 国内予選2003D Building a Space Station AOJ1127

解法：Union-Findでそれぞれのcell同士つながってるかをわかるようにし、つながってないcall間で必要なcorridorの長さの最小値を求めそのcorridorを採用する。という処理をすべてのcellがつながるまで繰り返す。

小数の扱いが闇だった。printf使えば小数点以下の桁数指定できることを完全に忘れてて大変だった。

#include <bits/stdc++.h>
#include <map>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
 
const ll MOD=1e9+7;
const ll INF=1e18;
 
int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};


double cell[110][4];
double dist[110][110]; // お互いの距離

int par[110];//親
int rank2[110];//木の深さ

void init(int n){
  for(int i = 0;i < n;i++){
    par[i] = i;
    rank2[i] = 0;
  }
}

int find(int x){
  if(par[x] == x){
    return x;
  }else{
    return par[x] = find(par[x]);
  }
}

void unite(int x,int y){
  x = find(x);
  y = find(y);
  if(x == y) return;
  
  if(rank2[x] < rank2[y]){
    par[x] = y;
  }else{
    par[y] = x;
    if(rank2[x] == rank2[y])rank2[x]++;
  }
}

bool same(int x,int y){
  return find(x) == find(y);
}
  
  
  



int main(){
    int n;
    while(1){
        cin >> n;
        if(n == 0)break;
        init(n);
        for(int i = 0;i < n;i++){
            for(int j = 0;j < 4;j++){
                cin >> cell[i][j];
            }
        }
        for(int i = 0;i < n;i++){
            for(int j = i+1;j < n;j++){
                double xyz = 0.0,rsum = cell[i][3] + cell[j][3];
                for(int k = 0;k < 3;k++){
                    xyz += (cell[i][k]-cell[j][k])*(cell[i][k]-cell[j][k]);
                }
                if(rsum*rsum >= xyz){ // iとjはつながっている
                    unite(i,j);
                }else{
                    dist[i][j] = sqrt(xyz) - rsum;
                    dist[j][i] = sqrt(xyz) - rsum;
                }
            }
        }
        double ans = 0.0;
        while(true){
            int flag = 0;
            int a,b;
            double distmin = 1000000.0;
            for(int i = 0;i < n;i++){
                for(int j = i+1;j < n;j++){
                    if(same(i,j) == false && distmin > dist[i][j]){
                        a = i;
                        b = j;
                        distmin = dist[i][j];
                        flag = 1;
                    }
                }
            }
            if(flag == 0)break;
            unite(a,b);
            ans += distmin;
        }
       // ans += 0.00001;
        //cout << round(ans*1000)/1000  << endl;
        printf("%.3f\n",ans);
    }
}