はじめに

今回は宇宙の問題なのかー。なら闇を操る程度の能力を持つ私が解けばいいのかー？

45分 *1
WA: 2回

問題

原文: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1127

あなたは宇宙ステーション運営チームのメンバーであり、コンピュータプログラムを書くことが仕事である。

宇宙ステーションは「セル」と呼ばれるたくさんのユニットから成り立っている。すべてのセルは球体をしている。しかし、それぞれの大きさは違う。宇宙ステーションが正常に軌道に乗った後、それぞれのセルは所定の位置に固定されます。 2つのセルは、互いに接触しているか、重なることができます。極端にいうと、あるセルがほかのセルを完全に内包するようなことも可能ですが、基本的にそのようなことをする意味はありません。

すべてのセルはつながっている必要があります。セルAとセルBがあった時に、宇宙ステーションのクルーはAとBを行き来できなければならないからです。以下のいずれかの場合、クルーはAとBを行き来できます。

AとBがが触れているか重なっている
AとBが「通路」でつながっている
AからCに行き来ができ、さらにCからBに行き来ができる

どのセルのペアも行き来ができるような設計にしたいと思いますが、そのような設計は複数パターン考えられます。例えば、セルA, B, Cがあった時に、A-B, A-C と通路でつなぐパターンと、A-B, B-C と通路でつなぐパターンなどがあります。しかし、通路の建設コストはその長さによります。そこであなたは、合計のコストが最も小さくなるように通路を設置したいと考えています。

各セルについて、座標 (x, y, z) と半径 r が与えられるので、それらをすべてつなげる最小のコストを出力してください。

※出力は小数点以下3桁でおこなう。e.g.: 0.000

方針なのかー

最小全域木問題というやつなのかー
- すべての頂点を連結する中で辺の重みの総和が最小となるグラフを見つけるのだー
プリム法というアルゴリズムがあるのかー。そうなのかー。また後で調べるのだー。
- グラフの大きさによっては今回の手法でも間に合わない時があるのかー？

最終的に僕がたどり着いた方法は以下のアルゴリズムなのだー。

すべてのセル間にエッジを持つようなセルグラフを作る。辺の重みは、 セル間の距離 - 両方のセルの大きさ とする。ただし負にはならない。
エッジを重み昇順でソートする
エッジを順に見ていき、その両端がまだ連結されていなかったらそのエッジを採用する
セルが連結しているかどうかの判定にはUnion-Find Treeを使う

あと、出力が小数点以下3桁だと気づかずに、WAを2回出してしまったのだー。0の場合も0.000を出力しなければいけないのだー。

実装なのかー

class Main {
    static HashMap<String, String[]> groups;
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(new InputStreamReader(System.in));
        while(true) {
            int n = sc.nextInt();
            if(n == 0) break;
            
            Cell[] cell = new Cell[n];
            for (int i = 0; i < n; i++) {
                double x = sc.nextDouble();
                double y = sc.nextDouble();
                double z = sc.nextDouble();
                double r = sc.nextDouble();
                cell[i] = new Cell(x, y, z, r);
            }
            
            ArrayList<Isle> arr = new ArrayList<Isle>();
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < i; j++) {
                    // コストを求める。
                    double xx = sq(cell[i].x - cell[j].x);
                    double yy = sq(cell[i].y - cell[j].y);
                    double zz = sq(cell[i].z - cell[j].z);
                    double dist = Math.sqrt(xx + yy + zz) - Math.abs(cell[i].r + cell[j].r);
                    dist = Math.max(0, dist);
                    Isle isle = new Isle(i, j, dist);
                    arr.add(isle);
                }
            }
            
            // コストでソート
            Collections.sort(arr, new IsleComp());
            
            int nn = arr.size();
            double ans = 0;
            UnionFindTree uft = new UnionFindTree(nn+1);
            for (int i = 0; i < nn; i++) {
                Isle isle = arr.get(i);
                if(uft.same(isle.x, isle.y)) continue;
                // sameでなければcostを払って連結
                ans += isle.cost;
                uft.unite(isle.x, isle.y);
            }
            
            System.out.printf("%.3f\n", ans);
        }
    }

    /**
    * 二乗
    */
    public static double sq(double d) {
        return d * d;
    }
}

/**
 * セル
 */
class Cell {
    double x, y, z, r;

    public Cell(double x, double y, double z, double r) {
        this.x = x;
        this.y = y;
        this.z = z;
        this.r = r;
    }
}

/**
 * セルをコストでソートする用
 */
class Isle {
    int x, y;
    double cost;
    public Isle(int x, int y, double dist) {
        this.x = x;
        this.y = y;
        this.cost = dist;
    }
    @Override
    public String toString() {
        return x + " " + y + " " + cost;
    }
}

class IsleComp implements Comparator<Isle> {
    @Override
    public int compare(Isle a, Isle b) {
        if(a.cost == b.cost){
            return 0;
        }else if(a.cost > b.cost){
            return 1;
        }else{
            return -1;
        }
    }
}

/**
 * UnionFindTree 
 */
class UnionFindTree {
    public int[] parent, rank;
    public int n;
    public int count;

    // 初期化
    UnionFindTree(int n) {
        this.n = n;
        count = n;
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }

    // 根を求める
    int find(int x) {
        if (parent[x] == x) {
            return x;
        } else {
            return parent[x] = find(parent[x]);
        }
    }

    // xとyの集合を結合
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return;
        }
        if (rank[x] < rank[y]) {
            parent[x] = y;
            count--;
        } else {
            parent[y] = x;
            if (rank[x] == rank[y])
                rank[x]++;
            count--;
        }
    }

    // xとyが同じ集合か
    boolean same(int x, int y) {
        return find(x) == find(y);
    }
}