GCJ2016 Round1B C.Technobabble

問題

N個の単語ペアが与えられる。ペアは前側と後ろ側の単語と区別する。
これは、N人が順番に、前側、後ろ側どちらかがそれまでその側で使われていない新しい単語を使って作られるようにしたはずのものである。
しかし、fakerと呼ばれる人はそれまで出てた単語を組み合わせて単語ペアを作ってしまっていた。
最大でfakerは何人いたと考えられるか？

small: 1<=N<=16
large: 1<=N<=1000

考え方

smallは、fakerかどうかをbitで表し、2^16試す。fakerじゃない＆faker条件を満たす集合かどうかを確認して、満たす場合の最大faker数を返す。

largeは、使うすべての単語を最小のペア数で抑えたとき、fakerじゃない集合(ちゃんと新しい単語で作った人)の数になるので、「N-(使うすべての単語をカバーできる最小のペア数)」が答えになっている。
(これは、2部グラフの頂点被覆最小辺カバー問題になっている。)

まず、前側、後ろ側で頂点が1度だけ使われるように辺を選びたいので、最大マッチングを取る。
このとき、マッチングに選ばれなかった頂点があるはずだが、これは新しい単語を使ったものなので、fakerにはなりえない。
したがって、「最大マッチング数＋最大マッチングで選ばれなかった頂点数」が「使うすべての単語をカバーできる最小のペア数」となる。
(「最大マッチング数+最小辺カバー数=頂点数」という性質を使えば、「最小辺カバー数=頂点数-最大マッチング数=左右の単語数合計-最大マッチング数」でも求められる。Nから個最小辺カバー数を引けば答え)