SRM557 Div1 550

問題

あなたはQBで、普通の少女を魔法少女にできる。
n人の普通の少女と、少女iが少女jを好き(非対称)、というリストが与えられる。
ある普通の少女iが魔法少女になったとき、その少女が好きな女性をプロテクト状態にでき、プロテクトされた少女の好きな少女も同様にすべてプロテクト状態になる。

プロテクト状態じゃない魔法少女の数が最大になるようにしたい。最大数を求める。

考え方

まず、「プロテクト状態じゃない」魔法少女が作りたいので、選ぶと同時にプロテクト状態になる自己ループのような少女は選べないので、除外。
また、少女iが誰かから好かれている場合、少女iを魔法少女にするとプロテクト状態にならないように、少女iを好きな少女とその少女を好きな少女...と再帰的に選べなくなる。

有向グラフを考える。再帰的に影響する点が決まるので、その影響する点に辺を張る(推移できる点への辺を張る)。
これはnが小さいので、Warshall-Floyd法で求められる。
ここで、ループが存在する(自分へ戻れるようなパスを持つ)頂点はプロテクト状態になるので選べないので除外。
最終的に、求めたいのは「2頂点間にパスが存在しないような頂点の最大数」になる。

ループできる点を除外しているので、DAGになっており、以下の定理が使える。

推移的に得られる辺を付け加えたDAGに対して、
「任意の2頂点間にパスが存在しないような頂点の部分集合の最大数」＝「最小パス被覆の本数」

最小パス被覆とは、どの頂点も少なくとも辺集合Fに属する辺につながっているとき、その辺数が最小となる時の辺の数をいう。

孤立点を含まないグラフにおいて、「|最大マッチング|＋|最小パス被覆|＝頂点数」が成り立つ。
孤立点はプロテクトされていない魔法少女として選べるので、それを除外し、孤立点を含まないDAGが作れるので、
このDAGで最大マッチングを求めることで、最小パス被覆の本数＝求めたい最大頂点数、が求められる。

DAGでの最大マッチングは、頂点集合Vについて、V'という仮想的なVのコピーの頂点集合を考え、Vの頂点vからwへの辺が存在したとき、vからV'でwに対応する頂点w'に辺を張る、のようにVとV'からなる2部グラフとして扱うことで、2部グラフの最大マッチング＝最大フローで求められる。|V|から引くことで、最小パス被覆の本数が求められ、孤立点の数との和が答えになる。