フローの問題を履修しているときに出くわしましたが、解説とちょっとグラフの作り方が違ったので。
解法
葉であるマス目を頂点として同じ行or同じ列どうしの頂点を辺で接続し、フローグラフを構築する。
すると、Sourceを、Destinationを
としたときの最小カットを求めることで、問題の解を求めることができる。
今回はどのように容量を持たせるかというところが問題だが、問題設定的に葉(=頂点)を落とさないといけないので、頂点が容量を持てるとうれしい。
そこで、各頂点をの2つに分割し、他の頂点から接続されるポイントを
に集約し、逆に他の頂点へ向かうポイントを
に集約する。さらに、
の間を容量
の辺で接続する。他の頂点への辺の容量は
としておく。
このようなフローグラフのボトルネックは必ず各頂点のの間になってくれるので、
から
に向かってフローを流すことで、それらの中のどれかがカットされ、答えが求まる。
注意する点としては、と
が同じ行or同じ列にある場合は
を出力する必要があるが、これはグラフ構築の時点で取り除かないと良くないことが起こると思われる。
(実装次第だと思うが、最小カットがになって出力されたり、フローライブラリの中でオーバーフローを起こしてヘンテコな値が出てくるかもしれない)
頂点数が、辺の数が最悪で
となるので、Dinic法で解くとすると
であるから、
程度か？
本当に間に合うんか？と疑いたくなるが、Dinic法に祈りながら提出すると、別にTLギリギリということはなく余裕でACになる。
実装例は以下の通り。
