アルゴリズム忘備録

競技プログラミングとかデータ分析とか

ARC074 F - Lotus Leaves

arc074.contest.atcoder.jp

 

2次元マップ上の複数の場所oとスタートとゴールが与えられる。が与えられる。x軸またはy軸が等しい場所o及びスタート、ゴールはワープすることができる。このとき、スタートからゴールにたどり着けなくするためにoを取り除きたい(スタートとゴールは取り除けない)。取り除くoの数の最小値はいくつか。全部取り除いてもたどり着けてしまう場合は-1を出力せよ。

 

取り除く最小値なので、互いに行き来できるo及びスタート、ゴールにエッジをつなぐことで何らかのグラフを構成し、最小カットという方針がうかぶ。

ただし、例えばoをノードにして同じ行や列にあるノードをクリークにする、という方針では最小カットで考えにくい(最小カットはあくまでもエッジをカットするということであり、ノードの除去はこの方針に対応しない。

そこで、[1, ... , H]及び[1, ..., W]という列及び行という(H+W)要素をノードとして、o間の移動はこの要素を経由して移動するという考え方をする。すると、これらのノード間に対して、oをエッジだと思いグラフを構成すると、辺のコスト1とした時の最小カットの数が答えになる。辺の貼り方は両方向、スタート・ゴールのみ一方通行とすればよい。O(HW)。