(o_o)

ブログ。

AOJ2290 Attack the Moles

問題概要
問題文から明らかな最小費用流を感じる何か

解法
右手が左手より右側になければならない,という条件は無視できる.
最小費用流で解くにしても,如何せんグラフのサイズが大きい.
きっちり辺を張ると辺の数は O(N^2) くらいになってしまう.
ここで,いい感じに辺を削除することを考える.a -> b, b -> c って辺張ってたら a -> c は要らないよね,みたいな感じで.
辺の削除にかかる時間は,全通り試すと O(N^3) だが,前処理で簡単な配列処理としてやると 2sec もかからない.
後は DAG なので負コスト辺をいい感じに正に変換したら間に合う.



gistc7ec41028d61b3ac77cd