スタートから同じ行、同じ辺にINFの辺を貼るとWAになる
https://atcoder.jp/contests/arc074/tasks/arc074_d
スタートの頂点から同じ行、同じ辺にINFの辺を貼ると以下の図の場合にWAになります。
Sと蓮を繋ぐINFの辺で、Sではない方のただの蓮を削除したら1回削除してそれで終わりなのに、辺がINFのせいでただの蓮の両端の辺に1が流れてしまい、答えが2になります。ではどうしたらいいのでしょうか？
各行、各列ごとにリーダーのような頂点を追加する
例えば二つの蓮があって、(i,j)=(2,3)と(2,4)の蓮があるとします。このときi=2が同じなので、この二つの蓮同士からはお互いに移動できます。となるとこの二つの蓮を容量1の辺で繋ぐことになるのですが、ここで二つの蓮を繋ぐのではなく、i=2を代表する頂点のようなもの作成します、以降この頂点をリーダーとして呼びます(ユニオンファインドのリーダーと同じ意味ではないです、ユニオンファインドだと存在している頂点の一つをリーダーとしますが、この場合は新しい頂点を作成しそれをリーダーとしています)。
そしてこのリーダーに対してそれぞれの蓮を容量1の辺で結ぶと以下のようになります。
さてこれをした意味はあるのでしょうか？ではここでスタートの頂点を用意してみます。スタートの蓮を(2,5)とします。このスタートの頂点からリーダーに対してINFを結んでみます。
すると各蓮に対して容量1の辺を結ぶことができました。ここで先ほど正しく最大流が動かなかった場合のグラフをこのグラフに繋げてみます。j座標は具体的に書いていませんが、同じ横軸にあったらj座標は同じと思ってください。(無駄な頂点を削除しています)
こんな感じになります。説明のために最大流が正しく動かなかったグラフを90度回転しています。
さて、この場合最大流はどうなるでしょうか？緑色の線で動きを書いてみるとこんな感じになります(下に進んでいますが上に進んでも同じです)
というわけで1という正しい答えが出ていることがわかりました。実際に実装する際はiだけでなく、jに対してもリーダーを作成します。また、スタートとゴールの蓮を二つにわけて、「ただの蓮」と「スタートまたはゴールの蓮」として別々に管理すると実装が楽になります。なぜうまく動くのか理解できていないので説明を省きますが、各蓮の座標を持たずに、リーダー同士を辺で結ぶことにより頂点数を(H+W+2)個で済ませることができます。例えば(2,3)と(2,4)の蓮なら、i=2が同じなので、j=3とj=4のリーダーを容量1の辺で結びます。フランちゃんによるとリーダーの頂点同士を結ぶことで、辺を取り除く問題にできるみたいです。
https://twitter.com/flandre_comp/status/1414285916449886209
ちなみにリーダーのような頂点を持たずに移動できる蓮同士を全て辺で結ぶとTLEするらしいです、理由が理解できていないので見なかったふりをします。
https://drken1215.hatenablog.com/entry/2020/01/29/011100
おわりに
参考にしたツイート https://twitter.com/flandre_comp/status/1414285916449886209
イメージとして最小カットのとき「容量1の辺は削除できる」「容量INFは削除することができない」と覚えるといいかもしれません、今回の問題だと辺ではなく頂点を削除する問題ですが、リーダーを使えば辺に言い換えられるらしいのでほぼ同じ感じな気がします。
最後にACしたコードを張っておきます。
https://atcoder.jp/contests/arc074/submissions/52148443