問題
提出コード
解法
フローの典型っぽいマッチング問題です。
始点、終点と、赤青のカードそれぞれを表す頂点を用意し、始点→赤の頂点、青の頂点→終点に重み1の辺を張っておきます。
そして、任意の赤と青のカードのペアについて、取り除くことができるものについては、そのカードを表す赤の頂点から、青の頂点へ重み1の辺を張ります。
あとは、始点から終点への最大流を求めることができれば、答えとなります。
qiita.com
感想
最初変なDPを考えていたのですが、よくよく考えるとマッチング問題だなぁ、と思ったので上のけんちょんさんのサイトを思い出しました。
けんちょんさんは偉大です…
