UVa 13008 - Exposing corruption

Source

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)$ 程度.

C++によるスパゲッティなソースコード

この部分を表示するには表示権限を持つユーザーでログインする必要があります.


Current time: 2017年09月21日05時09分22秒
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)

ログイン: