AOJ 1127 - Building a Space Station

問題概要

座標(x,y,z)に半径rのスペースステーションがN個ある。このN個全てのスペースステーションを行き来するための最小距離を求めよ。なお、2つの距離はoverrapしている場合は0と見なす。

制約

• 1 ≤ N ≤ 100
• 0 < x, y, z < 100

解法

全ての2頂点間の距離を求めて、それをコストとした最小全域木を求める。

コード

#include <bits/stdc++.h>
 
using namespace std;
 
#define MAX_V 100
#define MAX_E 10000
 
int V,E,par[MAX_V],rank[MAX_V];
 
struct Colony{
  double x,y,z,r;
  Colony(){}
  Colony(double x,double y,double z,double r) : x(x),y(y),z(z),r(r) {}
};
 
struct Edge{
  int u,v;
  double dist;
  Edge(){}
  Edge(int u,int v,double dist) : u(u),v(v),dist(dist) {}
};
 
bool comp(const Edge &e1,const Edge &e2){
  return e1.dist < e2.dist;
}
 
Edge es[MAX_E];
 
void init(){
  for(int i = 0 ; i < V ; i++){
    par[i] = i;
    rank[i] = 0;
  }
}
 
int find(int x){
  if(par[x] == x){
    return x;
  }
  return par[x] = find(par[x]);
}
 
void unite(int x,int y){
  x = find(x);
  y = find(y);
 
  if(x == y) return;
 
  if(rank[x] < rank[y]){
    par[x] = y;
  }else{
    par[y] = x;
    if(rank[x] == rank[y]){
      rank[x]++;
    }
  }
}
 
bool same(int x,int y){
  return find(x) == find(y);
}
 
double kruskal(){
  sort(es,es+E,comp);
  init();
  double res = 0.0;
  for(int i = 0 ; i < E ; i++){
    Edge e = es[i];
    if(!same(e.u,e.v)){
      unite(e.u,e.v);
      res += e.dist;
    }
  }
  return res;
}
 
double getDist(const Colony &c1,const Colony &c2){
  return sqrt(pow(c1.x-c2.x,2)+pow(c1.y-c2.y,2)+pow(c1.z-c2.z,2))-c1.r-c2.r;
}
 
int main(){
  while(cin >> V,V){
    E = 0;
    double x,y,z,r;
    Colony C[MAX_V];
    for(int i = 0 ; i < V ; i++){
      cin >> x >> y >> z >> r;
      C[i] = Colony(x,y,z,r);
    }
     
    for(int i = 0 ; i < V ; i++){
      for(int j = i+1 ; j < V ; j++){
        double dist = getDist(C[i],C[j]);
        es[E++] = Edge(i,j,max(dist,0.0));
      }
    }
    printf("%.3f\n",kruskal());
  }
  return 0;
}