http://poj.org/problem?id=3692男女がお互いを知っている最大の集合を求める。 これは男女がお互いを知らない、ということはない最大の集合であるので、 知り合いではない男女を辺でつないで最大安定集合を求めれば良い。 あとは|最大安定集合|=V-|最大マッ…

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

http://poj.org/problem?id=1486完全マッチングに必ず使われる辺を答えればよい。 それはフローが流れた辺を削除したとき完全マッチングになるかどうかで判断すればよい。その際に押し戻すテクを使ってN-1のフローを作り、対象の辺の容量を0にしてdfsすると…