kacho65535の競プロメモ

Atcoderと戯れる予定のブログです

AOJ 1127 - Building a Space Station

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1127&lang=en

解法

各データセットが与えられるので、3次元空間におけるn個の球体に対し任意の2点間を結ぶような\frac{n(n-1)}{2}本のエッジを張った後、クラスカル法などにより最小全域木問題を解けばよい。

中心の座標及び半径がそれぞれ

(x,y,z,r)=(x1,y1,z1,r1),(x2,y2,z2,r2)

である2つの球間のコストは

cost=max(0.0,\sqrt{(x1-x2)^2+(y1-y2)^2+(z1-z2)^2}-(r1+r2))

となる。

コード

#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;
}