AOJ 1127 - Building a Space Station
問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1127&lang=en
解法
各データセットが与えられるので、3次元空間における個の球体に対し任意の2点間を結ぶような本のエッジを張った後、クラスカル法などにより最小全域木問題を解けばよい。
中心の座標及び半径がそれぞれ
である2つの球間のコストは
となる。
コード
#include <bits/stdc++.h> using namespace std; struct union_find { vector<long long> par; //親の番号 vector<long long> rank; //木の深さ(根のランクは0) vector<long long> siz; //要素xが根なら木の頂点数を格納する //初期化子リストを用いた初期化 union_find(long long N) : par(N), rank(N), siz(N) { for (long long i = 0; i < N; i++) { par[i] = i; rank[i] = 0; siz[i] = 1; } } //要素xが所属する木の根を再帰的に発見する long long root(long long x) { if (par[x] == x) return x; return par[x] = root(par[x]); //経路圧縮 } //要素xが属する木と要素yが属する木の併合 void unite(long long x, long long y) { long long rx = root(x); long long ry = root(y); if (rx == ry) return; //同じ木に属してたらそのまま if (rank[rx] < rank[ry]) { par[rx] = ry; //根がryの木に併合 siz[ry] = siz[rx] + siz[ry]; } else { par[ry] = rx; //根がrxの木に併合 siz[rx] = siz[rx] + siz[ry]; if (rank[rx] == rank[ry]) rank[rx]++; } } //要素xが属する木と要素yが属する木が同じならtrueを返す bool same(long long x, long long y) { return root(x) == root(y); } //要素xが属する木の頂点数を返す long long size(long long x) { return siz[root(x)]; } }; struct kruskal_edge { long long u; long long v; double cost; }; //辺のコストの大小を比較 bool kruskal_comp(const kruskal_edge &e1, const kruskal_edge &e2) { return e1.cost < e2.cost; } vector<kruskal_edge> kruskal_side; double kruskal(long long V, long long E) //V:頂点数,E:辺数 { sort(kruskal_side.begin(), kruskal_side.end(), kruskal_comp); //辺のコストが小さい順にソート union_find kruskal_tree(V); double kruskal_res = 0; for (long long i = 0; i < E; i++) { kruskal_edge ks = kruskal_side[i]; if (!kruskal_tree.same(ks.u, ks.v)) { kruskal_tree.unite(ks.u, ks.v); kruskal_res += ks.cost; } } return kruskal_res; } int main() { cout << fixed << setprecision(3); while (true) { long long n; cin >> n; kruskal_side.resize(n * (n - 1) / 2); if (n == 0) break; vector<double> x(n); vector<double> y(n); vector<double> z(n); vector<double> r(n); for (long long i = 0; i < n; i++) cin >> x[i] >> y[i] >> z[i] >> r[i]; long long now = 0; for (long long i = 0; i < n; i++) { for (long long j = i + 1; j < n; j++) { kruskal_side[now].u = i; kruskal_side[now].v = j; double X = x[i] - x[j], Y = y[i] - y[j], Z = z[i] - z[j], R = r[i] + r[j]; kruskal_side[now].cost = max(0.0, (sqrt(X * X + Y * Y + Z * Z) - R)); now++; } } cout << kruskal(n, n * (n - 1) / 2) << endl; } return 0; }