No.3699 引き抜き交渉
yuki2006
問題文最終更新日: 2026-08-27 23:06:45
チーム機能テストコンテスト
(順位表)
の他の問題:
問題文
$N$ 人の参加者を、甲と乙の $2$ つのチームに分けます。 参加者 $i$ を甲に入れると $a_i$ の、乙に入れると $b_i$ の利益が得られます。
さらに $M$ 組の仲の良い組があり、$j$ 番目の組 $(u_j, v_j)$ が別々のチームに分かれてしまうと $c_j$ の損失が発生します。 得られる利益の合計から損失の合計を引いた値の最大値を求めてください。
入力
$N\ M$ $a_1\ b_1$ $\vdots$ $a_N\ b_N$ $u_1\ v_1\ c_1$ $\vdots$ $u_M\ v_M\ c_M$
$1 \le N \le 500$
$0 \le M \le 5000$
$0 \le a_i, b_i \le 10^6$
$1 \le u_j < v_j \le N$
$0 \le c_j \le 10^6$
入力はすべて整数
出力
利益の合計から損失の合計を引いた値の最大値を出力してください。 最後に改行してください。
サンプル
サンプル1
入力
3 2 5 1 1 5 3 3 1 2 1 2 3 1
出力
12
参加者 $1$ を甲、参加者 $2, 3$ を乙にすると、利益は $5 + 5 + 3 = 13$ で、損失は別チームになった組 $(1, 2)$ の $1$ だけです。よって $13 - 1 = 12$ となり、これが最大です。全員を甲にすると損失は $0$ ですが、利益が $5 + 1 + 3 = 9$ にとどまります。
サンプル2
入力
2 1 10 0 0 10 1 2 100
出力
10
別々のチームにすると $10 + 10 - 100 = -80$ です。$2$ 人とも甲にすれば $10 + 0 = 10$、$2$ 人とも乙にすれば $0 + 10 = 10$ なので、$10$ が最大です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。