[1005] ACM Craft

🔗 質問リンク

https://www.acmicpc.net/problem/1005

🔍 問題の説明

西暦2012年!ついに2年間、多くの国民が待ち受けるゲームACMクラフト(Association of Construction Managerクラフト)が発売された.
このゲームは以前のゲームとは異なり、ACMクラフトは活気に満ちたゲームを行うために建物を建てる順番を決めていない.つまり、1ゲーム目と2ゲーム目で建物を建てる順番が異なる場合があります.試合が始まるたびに、建物を建てる順番が与えられます.また、どの建物にもDelayがあり、建て始めから完成まであります.

上の例を見てください.
今回のゲームでは以下の建設順序ルールが与えられている.1号棟が完成したら、2号と3号の建設を始めることができます.(同時進行可能)また、4号棟を建てるためには、2号棟と3号棟がすべて完成しなければ、4号棟の建設が開始されません.
そのため、4号棟の建設を完了するには、まず最初の1号棟を建てるのに10秒かかります.また、2号棟と3号棟が同時に建設を開始すれば、2号棟は1秒後には完成するが、3号棟はまだ完成していないため、4号棟は建設できない.3号棟が完成すると、その時は4号棟を建てることができ、4号棟が完成するのに120秒かかります.
プロゲーマーの崔柏俊は、恋人とのデートの費用を用意するため、西江大学杯ACM Craft大会に出場した.崔伯俊は華麗なコントロール能力を持っているので、すべての試合で特定の建物を建てさえすれば、必ずゲームで勝つことができる.しかし、ゲームごとに特定の建物を建てる順番が違うので、崔伯俊はがっかりした.白俊のためにプログラムを作り、最も速い時間で特定の建物を建てるのに必要な最短時間を見つけた.

⚠▼制限

建物の番号は1番からN番まで存在します.

快適な建物を建てる命令を下すには時間がかからないと仮定します.

建設の順序はすべての建物が建てられることです.

🗝 プール(言語:Java)

これは位相整合によって解決される問題である.同時に建設され、両者の中で最大の時間を区別するのは難しい.総じて(前の順序の建築完了時間+次の建築完了時間)は、常に最大値を比較して更新されます.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {
    private static StringBuilder answer = new StringBuilder();

    private static void lineUp(int n, int[] cost, int[] needed, List<Integer>[] edges, int target) {
        Queue<Integer> queue = new LinkedList<>();
        int[] done = new int[n + 1]; // 해당 인덱스 건물 건설완료 시간 기록 배열
        for (int i = 1; i <= n; i++) {
            if (needed[i] == 0) { // 가장 선행으로 필요한 건물(needed[i] = 0)찾아서 큐에 넣기
                queue.add(i);
                done[i] = cost[i]; // 시작하는 건물 건설에 걸리는 시간은 기본이 답
            }
        }
        // 위상 정렬
        while (!queue.isEmpty()) {
            int one = queue.poll(); // 선행 건물
            for (int another : edges[one]) { // 다음 예정 건물들
                needed[another]--; // 다음에 지을 건물의 선행 건물수를 줄이기
                if (needed[another] == 0) // 다음에 지을 건물의 선행 건물이 없으면 큐 추가
                    queue.add(another);
                done[another] = Math.max(done[another], done[one] + cost[another]); // 시간이 더걸리는 경우 발견하면 갱신
            }
        }
        answer.append(done[target]).append('\n'); // 정답 문자열 이어붙여 만들기
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        for (int i = 0; i < t; i++) {
            StringTokenizer st1 = new StringTokenizer(br.readLine(), " ");
            int n = Integer.parseInt(st1.nextToken()), k = Integer.parseInt(st1.nextToken());
            int[] cost = new int[n + 1];
            StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
            // 시간 배열
            for (int j = 1; j <= n; j++)
                cost[j] = Integer.parseInt(st2.nextToken());
            // 간선 입력
            List<Integer>[] edges = new ArrayList[n + 1];
            // 그래프 리스트 초기화
            for (int j = 1; j <= n; j++)
                edges[j] = new ArrayList<>();
            int[] needed = new int[n + 1]; // 각 인덱스 사람보다 키작은 사람 수
            for (int j = 1; j <= k; j++) {
                StringTokenizer st3 = new StringTokenizer(br.readLine(), " ");
                int before = Integer.parseInt(st3.nextToken()), after = Integer.parseInt(st3.nextToken());
                edges[before].add(after); // 먼저 건설할 건물의 다음 건물을 그래프에 넣기
                needed[after]++; // 선행으로 필요한 건물수 기록
            }
            lineUp(n, cost, needed, edges, Integer.parseInt(br.readLine()));
        }
        System.out.print(answer);
    }
}