phyllo’s algorithm note

レッドコーダーへの道のりは遠い。休んでる場合じゃない!

KUPC2016 E. 柵 / Fences

問題

H*Wのグリッドのいくつかのマスにヤギがいる。
ヤギは上下左右の隣接マスに移動できるが、移動先となるマスに柵がある場合は、その方向へは移動できない。
ヤギがグリッドの外に出ないようにするために必要な柵の最小個数を求めよ。

制約

1 <= H <= 100
1 <= W <= 100

解説

http://www.kupc.jp/editorial/2016/E.pdf


最小カットで求めることができる。

マスに柵を置くかどうかを扱うために、各マスをin頂点とout頂点に分解し、ヤギのいないマスの場合はinからoutを容量1でつなぎ、ヤギがいる場合は容量infでつなぐ。
ヤギのいないマスの場合は、さらに、out頂点から上下左右のマスのin頂点へ容量infでつなぐ。

最後に、s-tフローで扱うために、頂点sからグリッドの縁のマスのin頂点へ容量infでつなぎ、ヤギのいるマスのout頂点から頂点tへつないで、s-t最小カットを求めればよい。