ABC259 G - Grid Card Game (600)
コンテスト中の考察
何もしなければ0点なので大失敗が最善になることはない
最小費用流にしてコストを求めれば良い?
最大フロー最小カットでコストを求めれば良い?
良いペナルティのかけ方が分からない
解説の解法からの考察
正の点数は全て獲得した物としてそこからの原点だけを考えて最大フロー最小カットで考える
行、列の値の和を事前に求めておく
各行について
和が正ならsからそれだけの容量の辺を張り、全体の正の和に足す
和が負ならtから符号反転したそれだけの容量の辺を張る
各列について
和が正ならtからそれだけの容量の辺を張り、全体の正の和に足す
和が負ならsから符号反転したそれだけの容量の辺を張る
$ s,tからのコストの割り振りは燃やす埋める問題を見ながら考えたら気がするが思い出せない
各マス$ (i,j)について
値が負なら$ -\infinの辺を張る
そうでないなら$ a_{ij}の辺を張る
和からフローを流した結果を引いた値が答え