白駿アルゴリズム1516号:ゲーム開発

リンク

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

質問する

同社は今回、新しい戦略シミュレーションゲームの3準ゲームを開発することにした.コア部分はすでに開発済みで、各種族のバランスやゲーム時間全体の調整などの部分しか残っていない.
ゲームに入る時間は状況によって異なる可能性があるため、すべての建物を建てるのに要する最小限の時間を利用して近似することにした.もちろん、問題は簡単ではないかもしれません.あるビルを建てるためには、まず別のビルを建てる必要があるかもしれません.例えば、星間争覇の中に砦を建てるためには、まず砦を建てるので、先に建ててから砦を建てる.複数の建物を同時に建てることができます.
便利な資源が無限に多いと仮定し、建物の建設命令を下すには時間がかからない.

入力

第1列目は、建物の種類数N(1≦N≦500)を与える.次のN行は、各建物を建てるのに要する時間と、その建物を建てるためにまず建てる建物の番号を示しています.建物の番号は1からNまでで、各行は-1で終わります.各建物を建てるのに要する時間は100000以下の自然数です.すべての建物を建てる可能性のある入力のみが与えられます.

しゅつりょく

N個の建物の完成に要する最小時間を出力します.

入力と出力の例

プールコード(C++,4 ms)

#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define MAX 100001
#define INF 1e9+7
#define sz(a) int((a).size())
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using dbl = double;
using ldb = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using wector = vector<vector<int>>;


int main(){
  fastio;
	int n; cin >> n;
  vector<int> indegree(n),time(n);
  vector<int> dp(n);
  vector<int> adj[501];
  queue<int> q;
  for(int i = 0; i < n; i++){
    cin >> time[i];
    while(1){
      int x; cin >> x; // 먼저 지어야하는 것
      if(x == -1) break;
      indegree[i]++;  // i번째 정점의 간선의 갯수를 1증가
      adj[--x].pb(i); // x -> i
    }
    if(indegree[i] == 0){
      dp[i] = time[i];
      q.push(i);
    }
  }
  while(!q.empty()){
    auto cur = q.front(); q.pop();
    for(auto nxt : adj[cur]){
      dp[nxt] = max(dp[nxt], dp[cur] + time[nxt]);
      if(--indegree[nxt] == 0) q.push(nxt);
    }
  }
  for(auto i : dp) cout << i << "\n";
	return 0;
}

復習(4ミリ秒)

#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define sz(a) int((a).size())
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
using namespace std;
using ll = long long;
using ull = unsigned long long;
using dbl = double;
using ldb = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using wector = vector<vector<int>>;

vi adj[501];

int main(){
  fastio;
  int n; cin >> n;
  vi dp(n, 0),indegree(n, 0),time(n, 0);
  for(int i = 0; i < n; i++){
    cin >> time[i];
    while(1){
      int x; cin >> x;
      if(x == -1) break;
      indegree[i]++;
      adj[--x].pb(i);
    }
  }
  queue<int> q;
  for(int i = 0; i < n; i++){
    if(!indegree[i]){
      dp[i] = time[i];
      q.push(i);
    } 
  }
  while(!q.empty()){
    auto cur = q.front(); q.pop();
    for(auto nxt : adj[cur]){
      dp[nxt] = max(dp[nxt], dp[cur] + time[nxt]);
      if(--indegree[nxt] == 0) q.push(nxt);
    }
  }
  for(auto i : dp) cout << i << "\n";
  return 0;
}

これは以前解決したACM Craft問題と似ているが,すべて出力しなければならないという違いがある.