バックアップアルゴリズム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行は、試験例の個数Tを与える.各テストの例は次のとおりです.第1行は、建築個数Nと建築間の建築順序規則の合計個数Kを与える.(建物番号は1番からN番まであります)
第2列の各建物の建設に要する時間Dは空白である.3行目からK+2行目まで、建設手順X Yが与えられる.(これはX棟を建ててY棟を建てることが可能であることを意味します)
最後の列は白俊が勝利のために建てた建物の番号Wを示した.

しゅつりょく

建物Wの完成に要する最小時間を出力する.快適な建物を建てる命令を下すには時間がかからないと仮定します.
建設の順序はすべての建物が建てられることです.

入力と出力の例

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

#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define MAX 1001
#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 tc; cin >> tc;
  while(tc--){
    int n,k,w; cin >> n >> k;
    vi time(n),dp(n),indegree(n);
    vi adj[MAX];
    queue<int> q;
    for(int i = 0; i < n; i++) cin >> time[i];
    for(int i = 0; i < k; i++){
      int a,b; cin >> a >> b; --a,--b;
      indegree[b]++;
      adj[a].pb(b);
    }
    cin >> w;
    for(int i = 0; i < n; i++){
      if(indegree[i]) continue;
      dp[i] = time[i]; q.push(i);
    }
    while(!q.empty()){
      auto cur = q.front(); q.pop();
      for(auto nxt : adj[cur]){
        // dp식
        dp[nxt] = max(dp[nxt], dp[cur] + time[nxt]);
        if(--indegree[nxt] == 0) q.push(nxt);
      }
    }
    cout << dp[--w] << "\n";
  }
	return 0;
}

復習(192ミリ秒)

#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>>;

int main(){
  fastio;
  int tc; cin >> tc;
  while(tc--){
    int n,k,w; cin >> n >> k;
    vector<int> indegree(n),time(n),dp(n);
    vi adj[1001];
    queue<int> q;
    for(int i = 0; i < n; i++) cin >> time[i];
    for(int i = 0; i < k; i++){
      int a,b; cin >> a >> b; --a,--b;
      indegree[b]++;
      adj[a].pb(b);
    }
    for(int i = 0; i < n; i++){
      if(!indegree[i]){
        dp[i] = time[i];
        q.push(i);
      }
    }
    cin >> w;
    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);
      }
    }
    cout << dp[--w] << "\n";
  }
  return 0;
}

これは,位相整列の順序でdpアレイを更新すれば,以前に解決した問題と同様である.