Fake scoreboard (UVa Live Archive Europe Southwestern 2010)
問題
オンラインジャッジのスコアボードの、各行と各列に何個ACがあるかの情報が与えられる。スコアボードを修復せよ。複数の解がある場合は辞書順最小の物を選べ。
1<=行、列<=80
解法
最大流でスコアボードに解が存在するか分かる。辞書順最小は、左上から順にそこの箇所がNに出きるか調べる。これはその辺がYの場合はそこを通る閉路が存在すれば、その閉路に水を流してその箇所がNのスコアボードにする。それぞれの箇所の値を決定した後は、capacityを0にしてそこに水が流せないようにしておく。