POJ 1466: Girls and Boys

http://poj.org/problem?id=1466最大安定集合を求める。 二部グラフになるので|最小点カバー|=|最大マッチング|、 任意のグラフについて|最小点カバー|+|最大安定集合|=|V|よりできる。 頂点を2倍にしてあげると実装が楽。 簡単な証明いろいろ。 |最大マッチング|+|最小辺カバー|=|V…