ゆらのふなびと

競プロ, Python, C++

AOJ-ICPC 300 Building a Space Station

問題

n個の球がある。球iは中心(x_i, y_i, z_i), 半径r_iである。これらの球の間に必要であれば橋を架けることで、すべての球の間を連結にしたい。ただし最初から共有点を持つ球どうしや、片方がもう片方を内包するような球どうしは既に連結であるとみなす。

すべての球を連結にするとき、橋の長さの総和の最小値を求めよ。

制約

  • 1 <= n <= 100
  • 0 < x, y, z, r < 100.0

解法

球iと球jを連結にするのに必要な最小の橋の長さをc_ijとする。球を頂点とし、球iと球jの間にコストc_ijの辺を張ったグラフを考えると、この問題は最小全域木問題に帰着できる。c_ijの値は以下のようになる。

  1. 球iと球jが共有点を持つor片方がもう片方を内包するとき、c_ij = 0
  2. それ以外のとき、c_ij = d_ij - r_i - r_j (ただしd_ijは球iと球jの中心間の距離)

円の位置関係は、d_ij > r_i + r_j のとき2、それ以外のとき1となる。よって1と2をまとめて c_ij = max(0, d_ij - r_i - r_j) としてよい。

#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()

typedef long long ll;
typedef pair<int, int> Pii;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;

const double EPS = 1e-10;

struct P {
    double x, y, z;
    P(){}
    P(double _x, double _y, double _z) : x(_x), y(_y), z(_z) {}
    const P operator+ (const P& p) {
        return P(this->x + p.x, this->y + p.y , this->z + p.z);
    }
    const P operator- (const P &p) {
        return P(this->x - p.x, this->y - p.y , this->z - p.z);
    }
    void print() {
        printf("%.1f %.1f %.1f\n", x, y, z);
    }
};

struct C {
    P c;
    double r;
    C(){}
    C(P _c, double _r) : c(_c), r(_r) {}
    C(double _x, double _y, double _z, double _r) : C(P(_x, _y, _z), _r) {}
};

double distancePP(P p, P q) {
    return sqrt((p.x - q.x) * (p.x - q.x)
            + (p.y - q.y) * (p.y - q.y)
            + (p.z - q.z) * (p.z - q.z));
}

double distanceCC(C c1, C c2) {
    return max(0., distancePP(c1.c, c2.c) - c1.r - c2.r);
}

C readC() {
    double x, y, z, r;
    cin >> x >> y >> z >> r;
    return C(P(x, y, z), r);
}

class UnionFind {
private:
    int n;
    vector<int> uni;
public:
    UnionFind(int _n) {
        n = _n;
        uni.clear();
        uni.resize(n, -1);
    }
    int root(int x) {
        if (uni[x] < 0) return x;
        return uni[x] = root(uni[x]);
    }
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    void unite(int x, int y) {
        x = root(x);
        y = root(y);
        if (x == y) return;
        if (uni[x] > uni[y]) swap(x, y);
        uni[x] += uni[y];
        uni[y] = x;
    }
    void print() {
        for (auto x : uni) cout << x << " ";
        cout << endl;
    }
};

template <typename T>
struct edge {
    int from, to;
    T cost;
    edge(){}
    edge(int _from, int _to, T _cost) : from(_from), to(_to), cost(_cost) {}
    bool operator< (const edge& e) const {
        return cost == e.cost ? (from == e.from ? to < e.to : from < e.from) : cost < e.cost;
    }
};

template <typename T>
class Kruskal {
private:
    int n;
    vector<edge<T>> edges;
    UnionFind uf;
public:
    Kruskal(int _n) : n(_n), uf(UnionFind(n)) {}
    void addEdge(int _from, int _to, T _cost) {
        edges.emplace_back(_from, _to, _cost);
    }
    T calc() {
        sort(all(edges));
        T res = 0;
        for (auto &e : edges) {
            if (!uf.same(e.from, e.to)) {
                uf.unite(e.from, e.to);
                res += e.cost;
            }
        }
        return res;
    }
};
/* !!!!! T: 辺のコストの型(int, double) !!!!! */

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int n;
    while (cin >> n, n) {
        vector<C> circles;
        rep(i, n) {
            circles.emplace_back(readC());
        }

        Kruskal<double> kr(n);
        rep(i, n) {
            rep2(j, i + 1, n) {
                kr.addEdge(i, j, distanceCC(circles[i], circles[j]));
            }
        }
        printf("%.3f\n", kr.calc());
    }
}

最小全域木はプリム法で書いた方が短くていいかもしれない。