AOJ 1127: Building a Space Station

問題

Building a Space Station | Aizu Online Judge

• 宇宙ステーションの各ユニットを全てつなぎたい
• 各ユニットは座標(x, y, z)に存在し、半径がrの球形である。球が接触していない場合は廊下でつなぐ必要がある
• 必要な廊下の長さの最小値を求めよ

方針

• いわゆる最小全域木の問題
• 各辺の長さはmin(0, 中心間距離-2球の半径の和)と表される
• 辺が密なのでプリム法を使う

コード

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)

double cost[101][101];
double mincost[101];
bool used[101];
double x[101], y[101], z[101], r[101];
double INF = numeric_limits<double>::max();
int main(void){
    int n;
    while(cin >> n && n) {
        rep(i, n) {
            cin >> x[i] >> y[i] >> z[i] >> r[i];
        }
        rep(i, n) rep(j, n) {
            cost[i][j] = max(sqrt(pow(x[i]-x[j], 2.0) + pow(y[i]-y[j], 2.0) + pow(z[i]-z[j], 2.0)) - r[i] - r[j], 0.0);
        }
        // prim
        rep(i, n) {
            mincost[i] = INF;
            used[i] = false;
        }
        mincost[0] = 0;
        double res = 0;

        while(true) {
            int v = -1;
            rep(u, n) {
                if(!used[u] && (v==-1 || mincost[u] < mincost[v])) v = u;
            }
            if(v == -1) break;
            used[v] = true;
            res += mincost[v];

            rep(u, n) {
                mincost[u] = min(mincost[u], cost[v][u]);
            }
        }
        printf("%.3lf\n", res);
    }
}

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1905345

反省

• プリム法が蟻本を見ないと書けなかった

クラスカルでも解いた

#include <bits/stdc++.h>
 
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
typedef long long int ll;
using namespace std;

struct UnionFind {
  vector<int> par;
  vector<int> rank;

  UnionFind(int n) : par(n), rank(n, 1) {
    for(int i=0; i<n; ++i) par[i] = i;
  }

  int find(int x) {
    if (x == par[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]) swap(x, y);
    par[y] = x;
    rank[x] += rank[y];
  }

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

typedef double Cost;

struct edge{
    int src, dst; Cost cost;
    edge(int s, int t, Cost c) : src(s), dst(t), cost(c) {}
    bool operator < (const edge &rhs) const {return cost < rhs.cost;}
};

Cost kruskal(int V, vector<edge> &edges) {
    UnionFind uf(V);
    sort(edges.begin(), edges.end());
    Cost ans = 0;
    for(auto e : edges) {
        if(!uf.same(e.src, e.dst)) {
            uf.unite(e.src, e.dst);
            ans += e.cost;
        }
    }
    return ans;
}

int main(void) {
    int n;
    while(cin >> n && n) {
        vector<double> x(n), y(n), z(n), r(n);
        vector<edge> edges;
        REP(i, n) {
            cin >> x[i] >> y[i] >> z[i] >> r[i];
        }
        REP(i, n)  {
            REP(j, n) {
                if(i == j) continue;
                double c = sqrt(pow(x[i]-x[j], 2.0) + pow(y[i]-y[j], 2.0) + pow(z[i]-z[j], 2.0)) - r[i] - r[j];
                edges.push_back(edge(i, j, max(0.0, c)));
            }
        }
        printf("%.3f\n", kruskal(n, edges));
    }
}

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2099226