AtCoder Regular Contest 074 F - Lotus Leaves
問題
グリッド上の池に葉がいくつか浮かんでいる。カエルは、同じ行/列にある葉を好きに行き来できる。葉を行き来できなくするよう、
以外の除く時の最小枚数を求める。
考察
葉からたどり着ける葉の集合
と、葉
からたどり着ける葉の集合
が互いに共通部分を持たないようにしたい。
に属する葉と
に属する葉が同じ行や列にあると、互いに行き来できてしまうので、どちらかを取り除いて、その行/列に属するのは
ないし
だけという状況を作り出せばよいことがわかる。
各行/列を頂点として、葉を行と列を結ぶ辺（容量1）とみなすと、より除く葉は
の最小カットと等しいことがわかる。
