Latin America Regional（20151115）
(ACM ICPC, Latin American Regional Contest)
UVa 13008
$2$ つの政党DSPとPPPがあり，DSPに所属する議員は $D$ 人，PPPに所属する議員は $P$ 人いる．
DSPの $i$ 番目の議員を買収するのにかかる金額 $S_i$ とPPPの $i$ 番目の議員を買収するのにかかる金額 $T_i$ が与えられる．
買収すると，違う政党に移動させることができる．
また，$R$ 個のライバル関係 $(d,p)$ が与えられ，DSPの $d$ 番目の議員とPPPの $p$ 番目の議員はライバルであるという意味である．
最終的には，ライバル同士は違う政党にいなければいけない．
予算が $B$ だけあるとき，うまく買収して，DSPの政党の議員数を最大化した場合何人になるか，PPPの政党の議員数を最大化した場合何人になるかをそれぞれ求める問題．
ライバル関係で結ばれている連結成分は，全部一緒に動かさなければいけないので，まとめておいて，コストいくらで，どちらをどれだけ増やせるかという情報にしておく．
後はナップサック問題になるのでDPで解けば良い．
時間計算量は $O(B(P+D)+R)$ 程度．
この部分を表示するには表示権限を持つユーザーでログインする必要があります．
Current time: 2024年04月20日09時16分05秒
Last modified: 2015年12月04日14時49分45秒 (by laycrs)
Tags: Competitive_Programming UVa_Online_Judge UVa_Contest_20151115_1
トップページに戻る
Logged in as: unknown user (not login)