結果

問題 No.3699 引き抜き交渉
コンテスト
ユーザー yuki2006
提出日時 2026-08-27 23:11:56
言語 JavaScript
(node v26.7.0 + ACL)
コンパイル:
true
実行:
node _filename_ ONLINE_JUDGE
結果
AC  
実行時間 61 ms / 2,000 ms
+ 746µs
コード長 2,427 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3 ms
コンパイル使用メモリ 6,400 KB
実行使用メモリ 63,820 KB
最終ジャッジ日時 2026-09-09 20:50:55
合計ジャッジ時間 2,098 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// プロジェクト選択問題(最小カット)。
//   総取り Σ(a_i + b_i) から「諦める分」を引く。諦める分の最小 = 最小カット。
//   S→i に a_i (i を乙にすると a_i を失う)
//   i→T に b_i (i を甲にすると b_i を失う)
//   i↔j に c_j (別チームになると c_j を失う。両向き c_j)
// 答え = Σ(a_i + b_i) - mincut
function maxflow(n, edges, s, t) {
  // Dinic。edges は [from, to, cap] の配列(逆辺は自動で張る)
  const head = new Int32Array(n).fill(-1);
  const nxt = [], to = [], cap = [];
  const addEdge = (u, v, c, rc) => {
    to.push(v); cap.push(c); nxt.push(head[u]); head[u] = to.length - 1;
    to.push(u); cap.push(rc); nxt.push(head[v]); head[v] = to.length - 1;
  };
  for (const [u, v, c, rc] of edges) addEdge(u, v, c, rc ?? 0);

  const level = new Int32Array(n);
  const iter = new Int32Array(n);
  const queue = new Int32Array(n);

  const bfs = () => {
    level.fill(-1);
    let qh = 0, qt = 0;
    level[s] = 0; queue[qt++] = s;
    while (qh < qt) {
      const v = queue[qh++];
      for (let e = head[v]; e !== -1; e = nxt[e]) {
        if (cap[e] > 0 && level[to[e]] < 0) { level[to[e]] = level[v] + 1; queue[qt++] = to[e]; }
      }
    }
    return level[t] >= 0;
  };

  const dfs = (v, f) => {
    if (v === t) return f;
    for (; iter[v] !== -1; iter[v] = nxt[iter[v]]) {
      const e = iter[v], u = to[e];
      if (cap[e] > 0 && level[v] < level[u]) {
        const d = dfs(u, Math.min(f, cap[e]));
        if (d > 0) { cap[e] -= d; cap[e ^ 1] += d; return d; }
      }
    }
    return 0;
  };

  let flow = 0;
  while (bfs()) {
    for (let i = 0; i < n; i++) iter[i] = head[i];
    let f;
    while ((f = dfs(s, Infinity)) > 0) flow += f;
  }
  return flow;
}

function solveF(input) {
  const d = input.split(/\s+/).filter(s => s.length);
  let p = 0;
  const n = +d[p++], m = +d[p++];
  const S = n, T = n + 1;
  const edges = [];
  let total = 0;
  for (let i = 0; i < n; i++) {
    const a = +d[p++], b = +d[p++];
    total += a + b;
    edges.push([S, i, a]);
    edges.push([i, T, b]);
  }
  for (let j = 0; j < m; j++) {
    const u = +d[p++] - 1, v = +d[p++] - 1, c = +d[p++];
    // 無向辺は「両方向に容量 c」で表す(逆辺も c)
    edges.push([u, v, c, c]);
  }
  return String(total - maxflow(n + 2, edges, S, T));
};

console.log(solveF(require("fs").readFileSync(0, "utf8")));
0