京都大学プログラミングコンテスト 2016 E. 柵
解法
解説スライド(分かりやすい): E.pdf
まず、元から端にヤギがいる場合は、どうやってもヤギは外へ出てしまうので、その場合は-1を出して終了する。
それ以外の場合を考える。
柵でヤギを囲むことを、頂点をヤギがいる側とそうでない側に分離する、と言い換える。
できるだけ、小さい数で分離したいので、つまりこれは、(厳密でない言い方をすれば)頂点に対する最小カットである。
このような場合は、1つの頂点を2つに分離し、その2つの頂点間に流量1の辺を張り、それ以外の辺には流量INFの辺を張ることによって、流量1のところのみからなる最小カットを考えることができる。(蟻本にも書いてあるらしい)
あとは、最小カット=最大フローの定理から、ヤギのいる頂点をsource、端の頂点をsinkとする最大フローを求めればよい。
計算量
頂点がかなり多いけど、流量がO(H+W)になるので大丈夫
コード
PythonだとPyPyじゃないとTLEする
感想
ABC010のDみたいに、最小で分離したい、みたいなのだと最小カット使えそう(まあ制約からも推測は可能?)
プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?
- 作者: 秋葉拓哉,岩田陽一,北川宜稔
- 出版社/メーカー: マイナビ
- 発売日: 2012/01/28
- メディア: 単行本(ソフトカバー)
- 購入: 25人 クリック: 473回
- この商品を含むブログ (36件) を見る