yukicoder No.1744 Selfish Spies 1 (à la Princess' Perfectionism)
解法
ACLのchange_edge()を利用した解法を説明します。
まず、最大マッチングを1つ求めます。この時、最大マッチングに含まれない辺は明らかにYesです。
以下、最大マッチングに含まれる辺についてのみ考えます。
最大マッチングに含まれる辺を取り除いてもマッチングの数が変わらなければYes、そうでなければNoです。
辺を取り除いて毎回($ L回)二部マッチングを解くと$ O(L^2 \sqrt(N+M))でTLEしてしまいます。
最大マッチングに含まれる辺の1つを$ (u, v) ($ uは左側の頂点(スパイ)、$ vは右側の頂点(任務))とします。また、$ S, Tをそれぞれネットワークのsource, sinkとします。
この時、$ S \rightarrow u, u \rightarrow v, v \rightarrow Tの辺は容量1、流量1のはずです。
これを、ACLのchange_edge()を用いて、
$ S \rightarrow u を容量1、流量0
$ u \rightarrow vを容量0、流量0
$ v \rightarrow Tを容量1、流量0
に変えて、もう1度$ S \rightarrow Tにフローを流します。
この時maxflowが1なら最大マッチングに含まれる辺を取り除いてもマッチングが1増えて最大マッチングを達成できるのでYes、maxflowが0なら達成できないのでNoとなります。
change_edge()をしてフローを流した後は、再びchange_edge()を適切に行ってフローを復元します。
計算量は正確に見積もっていませんが、多重辺が存在しないことと、毎回フローを流す際に使われる辺が$ u, vに接続された辺と$ S \rightarrow u, v \rightarrow Tのみで、流量が1であることから、$ O(L \sqrt(N+M) + L(N+M))とかで抑えられている気がしています(本当でしょうか、、、)