SnackDown 2017 Online Elimination Round
Cleaning the Space (SPCLN)
https://www.codechef.com/SNCKEL17/problems/SPCLN
この問題は
https://www.codechef.com/problems/RINと同値。問題設定や変数名を変えただけ。Editorialもある。
解法
最小カット問題として解く。
とりあえず各space debrisの最大エナジーをとり、他のボタンで破壊するならその分のペナルティを受けると考える。
依存関係を保つために流量INFを張ってペナルティを最小カットとして求める。
グラフは「燃やす埋める問題」を多層にした感じ。RINのEditorialが詳しい。
