[BOJ]2056タスク|位相合わせ,DP

11531 ワード
白駿 boj JavaScript アルゴリズム#アルゴリズム# 白駿2056 操作 js テキストリンク
Problem | 操作

アクセス方法

  • グラフを先に作成する.また,接続されたノードが0でない場合,自身からの度数を格納する.
  • queueにゼロ度のものを先に加え、dp配列で自分が実行するのに要する時間を初期化する.
  • queueでは、値を変換することで自分と接続するノードの度数を減らす.
    この場合,dpは自分に入力したtimeの最大値を必要とする.
    3を実行するためには、[3番ノードに接続されているノードを1,2,1番ノード(所要時間:6秒)、2番ノード(所要時間:3秒)とする]が、遅くとも6秒待たなければならないからである.
    • ・｢｣｢｢｣の完全コード・｢
    
const input = require("fs")
  .readFileSync(process.platform === "linux" ? "dev/stdin" : "./input.txt")
  .toString()
  .split("\n");

let n = Number(input[0]);
let graph = Array.from(Array(n + 1), () => Array());
let indegree = new Array(n + 1).fill(0);
let time = new Array(n + 1);

// 그래프 완성시키기
for (let i = 1; i <= n; i++) {
  let tmp = input[i].split(" ").map(Number);
  time[i] = tmp[0];
  if (tmp[1] !== 0) {
    // 추가할 것이 있는 경우
    for (let j = 2; j < tmp.length; j++) {
      graph[tmp[j]].push(i);
      indegree[i]++;
    }
  }
}

// indegree 0인 걸 초기화시켜주고, dp 초기값 초기화
let queue = [];
let dp = new Array(n + 1).fill(0);
for (let i = 1; i <= n; i++) {
  if (indegree[i] === 0) {
    queue.push(i);
    dp[i] = time[i];
  }
}
/*
console.log(dp);
console.log(queue);
*/
while (queue.length) {
  let x = queue.shift();
  for (let next of graph[x]) {
    indegree[next]--;
    dp[next] = Math.max(dp[next], dp[x] + time[next]);
    if (indegree[next] === 0) queue.push(next);
  }
}
console.log(Math.max(...dp));
    パーティションを持つ
    エクスプレスから始める