Fake scoreboard (UVa Live Archive Europe Southwestern 2010)

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=399&page=show_problem&problem=2958

問題

オンラインジャッジのスコアボードの、各行と各列に何個ACがあるかの情報が与えられる。スコアボードを修復せよ。複数の解がある場合は辞書順最小の物を選べ。
1<=行、列<=80

解法

最大流でスコアボードに解が存在するか分かる。辞書順最小は、左上から順にそこの箇所がNに出きるか調べる。これはその辺がYの場合はそこを通る閉路が存在すれば、その閉路に水を流してその箇所がNのスコアボードにする。それぞれの箇所の値を決定した後は、capacityを0にしてそこに水が流せないようにしておく。