白駿1005番 ACM Craft解答

問題の説明

西暦2012年!ついにこの2年間、無数の国民を待っていた. ACM Craft(Association of Construction Manager Craft)が発売された.
このゲームは以前のゲームとは異なり、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大会に出場した.崔伯俊は華麗なコントロール能力を持っているので、すべての試合で特定の建物を建てさえすれば、必ずゲームで勝つことができる. しかし、ゲームごとに特定の建物を建てる順番が違うので、崔伯俊はがっかりした. 白俊のためにプログラムを作り、最も速い時間で特定の建物を建てるのに必要な最短時間を見つけた.

問題を見る考え

ノードのアクセス順です.

位相でアクセスをソートする順序を決定します.

プールの概要

位相キャリブレーション後、アクセスノードの建設時間を保存し、

は同じレベルで最大時間をもたらします.

コード#コード#

#include <iostream>
#include <vector>
#include <queue>
#include <memory.h>
#include <algorithm>

#define MAX_N 1000

using namespace std;

int T, N, K, W;
int buildTime[MAX_N+1];
int dime[MAX_N+1];

int totalTime[MAX_N+1];
vector<int> build[MAX_N+1];
vector<int> comeBuild[MAX_N+1];

void initResource(){
  memset(buildTime, 0, sizeof(buildTime));
  memset(dime, 0, sizeof(dime));
  memset(totalTime, 0, sizeof(totalTime));

  for(int i=0; i<=MAX_N; ++i){
    vector<int> ().swap(build[i]);
    vector<int> ().swap(comeBuild[i]);
  }
}

void getInput(){
  cin >> N >> K;
  initResource();
  for(int i=1; i<=N; ++i){
    cin >> buildTime[i];
  }
  for(int i=1; i<=K; ++i){
    int l, r; cin >> l >> r;
    build[l].push_back(r);
    comeBuild[r].push_back(l);
    ++dime[r];
  }

  cin >> W;
}

vector<int> topologySort(){
  vector<int> v;
  queue<int> q;
  bool visit[MAX_N+1];
  memset(visit, false, sizeof(visit));

  for(int i=1; i<=N; ++i){
    if(dime[i] == 0){
      q.push(i);
    }
  }

  while(!q.empty()){
    int curr = q.front(); q.pop();
    if(visit[curr]){
      continue;
    }
    visit[curr] = true;

    v.push_back(curr);
    for(auto next: build[curr]){
      --dime[next];
    }
    for(int i=1; i<=N; ++i){
      if(dime[i] == 0){
        q.push(i);
      }
    }
  }

  return v;
}

int calcTime(vector<int> v){
  for(auto curr: v){
    totalTime[curr] += buildTime[curr];
    int maxi = 0;
    for(auto come: comeBuild[curr]){
      maxi = max(maxi, totalTime[come]);
    }
    totalTime[curr] += maxi;
  }

  return totalTime[W];
}

void solve(){
  getInput();
  vector<int> topSort = topologySort();
  cout << calcTime(topSort);
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> T;
  while(T--){
    solve();

    cout << "\n";
  }

  return 0;
}

ポスト

は、以前に実装されたコードであるため、解釈が異なる場合がある.もしあなたが私にフィードバックしてくれたら、私は感謝します.