[伯俊]ゲーム開発

11869 ワード
テキストリンク
質問リンク:https://www.acmicpc.net/problem/1516
位相整列の概念は久しぶりに考えられたので,基本的な位相整列問題をもたらした.
  • 位相整列とは?
    これは,順序付きタスクを順次実行する必要がある場合に,順序を決定するために用いられるアルゴリズムである.
    方法
  • を0の頂点に挿入します.
  • キューから要素を取り出し、接続されているすべての幹線を削除します.
  • チャネルがクリアされると、差が0の頂点がキューに挿入されます.
  • Qビル大学まで2番と3番のコースを繰り返します.すべての要素にアクセスする前にキューが空の場合はループがあり、すべての要素にアクセスした場合は、キューから取り出した順序が位相ソートの結果になります.
    • 上記の問題では,順序を決定する直接的なヒントはないが,建築上は前後関係があるため,順序を含む.
    #include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
// parent -> child
vector <int> graph[501];
queue <int> q;
int times[501];
// priors : i번째 건물을 짓는 데 필요한 건물의 수
int priors[501] = {0};
int result[501] = {0};
int n;

int main(void){
    int t, prior;
    cin >> n;
    for(int i = 1;i <= n;i++) {
        cin >> t;
        times[i] = t;
        while(1){
            cin >> prior;
            if(prior == -1) break;
            // 건물 하나 짓는데 그 이전에 지어야하는 건물이 여러 개일 가능성 존재
            priors[i]++;
            graph[prior].push_back(i);
        }
    }
    // 진입차수가 0인 노드를 큐에 우선 삽입
    for(int i = 1;i <= n;i++){
        if(priors[i] == 0){
            result[i] = times[i];
            q.push(i);
        }
    }
    // 위상 정렬이 완전히 수행되려면 n개의 노드 pop
    // 만약 큐가 먼저 empty되면 cycle이 있는 것이다.
    for(int i = 1;i <= n;i++){
        if(!q.empty()){
            int x = q.front();
            q.pop();
            for(int j = 0;j < graph[x].size();j++){
                int y = graph[x][j];
                result[y] = max(result[y], result[x] + times[y]);
                if(--priors[y] == 0){
                    q.push(y);
                }
            }
        }
    }
    
    for(int i = 1;i <= n;i++){
        cout << result[i] << endl;
    }
    
}
    上記位相ソートの概念を適用してこの問題を処理すると,建物ごとの建造に要する時間を入力し,まず建造する建物の個数preorを入力する.
    また,建物間の前後関係はチェーンテーブルとして格納される.
    既存と異なり、vectorの形式で行うとエラーが発生します.ベクトルのpush backメソッドは、push backを逆方向にするとメモリが生成されないためです.
    そこで今回はベクトルの配列形式でアクセスします.
    e.g. vector<int> graph[501]したがって、例の結果を以下のように可視化します.

    (画像処理が面倒)
    まだ位相合わせの仕方がわかっていないようなのでもう一問してから寝ます
    Mock Interview: Microsoft #8
    bootstrapのHello World