この問題は、カエルが移動する方法をなくす、という時点で最小カット問題を連想すると思います。
次に考えるのは、葉をグラフの頂点とみなして最小カットに似たことをする、という方針ですが、これをすると辺の張り方がわからなくなる上、そもそも一つの葉が一つの辺に対応していないので最小カット問題ではなくなり破綻します。
というわけで、葉をグラフの頂点ではなく、辺としてとらえて最小カットに帰着させる必要があります。
ここで、(x,y)に存在する葉の作用を考えてみましょう。
これは、「x行の別の列に居るカエルがy列に跳躍するための機関」「y列の別の行に居るカエルがx行に跳躍するための機関」の役割を果たします。
念頭に置くべきことが1つ、カエルの移動について、列の移動または行の移動の連続はカエルの移動のルール的に意味がないので、カエルの移動は行列交互というふうにみなすことができます。
というわけで、カエルの移動を「a行に居ることを利用してb列に跳躍する、b列に居ることを利用してc行に跳躍する」…の繰り返しで表現できることが分かりました。
すると、以下のようなグラフが描けます。
このグラフで、Sから最初に居る頂点を行のものにするか、列のものにするか(赤が行で、青が列です)を選んでから行列の移動を繰り返し、Tと同じ行または列にたどり着けばゴールです。
これで、各葉は「行aから列bまで移動するため、またはその逆をするための跳躍機関」として辺に対応付けることができました。
あとは有向辺の流量をinf、無向辺の流量を1としてDinicなりEdmons-KarpなりFord-Fulkersonなりお好きにどうぞ。
過去にDinic実装したらめちゃくちゃ重かったのでライブラリ化してます。しばらく書きたくないです
フローをソラで書くシチュは相当限られる(IOIシラバスで除外されているのでJOI/IOIで万一使うなら部分点狙いになる)と思うので理屈が分かっていればライブラリ化でいいと思います。
解説読んでしてやられた感が半端ないのでメモ。
