読者です 読者をやめる 読者になる 読者になる

AOJ 1127: クラスカル法で最小全域木問題を解く

問題

Building a Space Station | Aizu Online Judge

3次元空間にn個の球形の宇宙ステーションがあるので、それらを行き来する通路を作る際の、通路の最小合計距離を求める。

解法

2つの宇宙ステーション間の距離を求め、最小全域木探索する。

コード

import java.math.BigDecimal;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (true) {
            int n = sc.nextInt();
            if (n == 0) {
                sc.close();
                break;
            }

            double[][] stations = new double[n][4];
            for (int i = 0; i < stations.length; i++) {
                stations[i][0] = sc.nextDouble();
                stations[i][1] = sc.nextDouble();
                stations[i][2] = sc.nextDouble();
                stations[i][3] = sc.nextDouble();
            }

            PriorityQueue<Edge> edges = new PriorityQueue<Edge>();
            for (int i = 0; i < n; i++) {
                for (int j = i + 1; j < n; j++) {
                    double x1 = stations[i][0];
                    double x2 = stations[j][0];
                    double y1 = stations[i][1];
                    double y2 = stations[j][1];
                    double z1 = stations[i][2];
                    double z2 = stations[j][2];
                    double r1 = stations[i][3];
                    double r2 = stations[j][3];

                    double dist = Math.sqrt(Math.pow((x1 - x2), 2)
                            + Math.pow((y1 - y2), 2) + Math.pow((z1 - z2), 2))
                            - r1 - r2;
                    dist = Math.max(dist, 0);
                    edges.add(new Edge(dist, i, j));
                }
            }

            // クラスカル法
            UnionFind uf = new UnionFind(n);
            double cost = 0;
            while (!edges.isEmpty()) {
                Edge e = edges.poll();
                if (!uf.isSame(e.from, e.to)) {
                    cost += e.weight;
                    uf.unite(e.from, e.to);
                }
            }

            BigDecimal bd = new BigDecimal(String.valueOf(cost));
            System.out.println(bd.setScale(3, BigDecimal.ROUND_HALF_UP));

        }
    }
}

class UnionFind {
    int[] parts;

    UnionFind(int n) {
        parts = new int[n];
        for (int i = 0; i < n; i++)
            parts[i] = i;
    }

    public int find(int x) {
        if (parts[x] == x)
            return x;
        return parts[x] = find(parts[x]);
    }

    public Boolean isSame(int x, int y) {
        return find(x) == find(y);
    }

    public void unite(int x, int y) {
        if (find(x) == find(y))
            return;
        parts[find(x)] = find(y);
    }
}

class Edge implements Comparable<Edge> {
    double weight;
    int from, to;

    Edge(double w, int f, int t) {
        this.weight = w;
        this.from = f;
        this.to = t;
    }

    @Override
    public int compareTo(Edge edge) {
        // 昇順
        if (this.weight > edge.weight) {
            return 1;
        } else if (this.weight == edge.weight) {
            return 0;
        } else {
            return -1;
        }
    }
}