n-knuu's logs

憧れ駆動。だいたい競プロ

京都大学プログラミングコンテスト 2016 E. 柵

解法

解説スライド(分かりやすい): E.pdf

まず、元から端にヤギがいる場合は、どうやってもヤギは外へ出てしまうので、その場合は-1を出して終了する。

それ以外の場合を考える。
柵でヤギを囲むことを、頂点をヤギがいる側とそうでない側に分離する、と言い換える。
できるだけ、小さい数で分離したいので、つまりこれは、(厳密でない言い方をすれば)頂点に対する最小カットである。
このような場合は、1つの頂点を2つに分離し、その2つの頂点間に流量1の辺を張り、それ以外の辺には流量INFの辺を張ることによって、流量1のところのみからなる最小カットを考えることができる。(蟻本にも書いてあるらしい)
あとは、最小カット=最大フローの定理から、ヤギのいる頂点をsource、端の頂点をsinkとする最大フローを求めればよい。

計算量

頂点がかなり多いけど、流量がO(H+W)になるので大丈夫

コード

PythonだとPyPyじゃないとTLEする

感想

ABC010のDみたいに、最小で分離したい、みたいなのだと最小カット使えそう(まあ制約からも推測は可能?)

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?