[白俊]#2887惑星トンネル

質問する

2040年、李ミンヒョクは宇宙で自分の王国を創造した.王国はN個の惑星からなる.この惑星を効果的に支配するために、ミンヘは惑星を結ぶトンネルを建設しようとした.
惑星は3次元座標上の点とされている.2つの惑星A(xA、yA、zA)とB(xB、yB、zB)をトンネルに接続するのに要する費用はmin(|xA-xB|、|yA-yB|、|zA-zB|)である.
ミンヘは全部でN-1のトンネルを建てて、すべての惑星を互いに接続させたいと思っています.このとき、すべての惑星をトンネルに接続するのに必要な最低コストを求めるプログラムを作成してください.

入力

最初の行は惑星の個数Nを与える.(1≦N≦100000)次のN行は、各惑星のx、y、z座標を与える.座標は-109以上、または109未満の整数です.1つの位置に2つ以上の惑星はありません.

しゅつりょく

1行目の出力ですべての惑星をトンネルに接続するのに必要な最小コスト.

入力例1

5
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19

サンプル出力1

4

に答える

この問題はMST(最小生成ツリー)問題であり,クルーズアルゴリズムで解くことができる.この問題では,X,Y,Zの順に並べ替えてキューに入れることで,時間とメモリを減らすことができる.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Main {
    static int[] parent;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Planet[] planets = new Planet[N];

        for(int i=0; i<N; i++) {
            String[] input = br.readLine().split(" ");
            planets[i] = new Planet(Integer.parseInt(input[0]), Integer.parseInt(input[1]), Integer.parseInt(input[2]), i);
        }

        PriorityQueue<Pair> pq = new PriorityQueue<>();
        parent = new int[N];
        for(int i=0; i<N; i++)
            parent[i] = i;

        Arrays.sort(planets, Comparator.comparingInt(p -> p.x));

        for(int i=0; i<N-1; i++) {
            Planet p1 = planets[i];
            Planet p2 = planets[i+1];

            pq.add(new Pair(p1.idx, p2.idx, Math.abs(p1.x-p2.x)));
        }

        Arrays.sort(planets, Comparator.comparingInt(p -> p.y));

        for(int i=0; i<N-1; i++) {
            Planet p1 = planets[i];
            Planet p2 = planets[i+1];

            pq.add(new Pair(p1.idx, p2.idx, Math.abs(p1.y-p2.y)));
        }

        Arrays.sort(planets, Comparator.comparingInt(p -> p.z));

        for(int i=0; i<N-1; i++) {
            Planet p1 = planets[i];
            Planet p2 = planets[i+1];

            pq.add(new Pair(p1.idx, p2.idx, Math.abs(p1.z-p2.z)));
        }


        int ans = 0;
        while(!pq.isEmpty()) {
            Pair temp = pq.poll();

            int x = temp.x;
            int y = temp.y;

            if(find(x)==find(y)) continue;

            union(x, y);

            ans += temp.cost;
        }

        System.out.println(ans);
    }

    public static void union(int a, int b) {
        a = find(a);
        b = find(b);

        if(a<b)
            parent[b] = a;

        else
            parent[a] = b;
    }

    public static int find(int a) {
        if(parent[a]==a)
            return a;

        return parent[a] = find(parent[a]);
    }

    public static class Planet {
        int x;
        int y;
        int z;
        int idx;

        public Planet(int x, int y, int z, int idx) {
            this.x = x;
            this.y = y;
            this.z = z;
            this.idx = idx;
        }
    }

    public static class Pair implements Comparable<Pair>{
        int x;
        int y;
        int cost;

        public Pair(int x, int y, int cost) {
            this.x = x;
            this.y = y;
            this.cost = cost;
        }

        public int compareTo(Pair p) {
            return this.cost > p.cost ? 1 : -1;
        }
    }
}