POJ 1466: Girls and Boys

Flow

http://poj.org/problem?id=1466

最大安定集合を求める。
二部グラフになるので|最小点カバー|=|最大マッチング|、
任意のグラフについて|最小点カバー|+|最大安定集合|=|V|よりできる。
頂点を2倍にしてあげると実装が楽。



簡単な証明いろいろ。

  • |最大マッチング|+|最小辺カバー|=|V|

辺を追加すると新たにカバーできる点は2つor1つor0つ。0つは明らかに無駄であり、なるべく2つずつカバーしたい。
ここで2つずつカバーできる最大回数=|最大マッチング|なので残りの点はそれらと同じ数だけの辺でカバーする。
これで最小辺カバーが得られる。よって
|最小辺カバー| = (新たに1つ点をカバーする辺)+(2つ点をカバーする辺)=(V-2*M)+M=V-M (M=|最大マッチング|)となり示せた。

  • |最小点カバー|+|最大安定集合|=|V|

XがGの安定集合<=>V-XがGの点カバー を示す。
(=>)V-Xはある辺を通じてXと必ずつながっている。なぜならXの点どおしは互いに隣接しておらず、V-Xの点によって囲われているから。
(<=)もしXに隣接している2点が存在したとすると、その間の辺はカバーできておらず、V-Xが点カバーであることに矛盾。
よって|点カバー|+|安定集合|=|V|であり、点カバーが最小なら安定集合は最大となるので示せた。

  • 二部グラフ(U,V)において|最大マッチング|=|最小点カバー|

最大マッチングにより|S|-|Γ(S)|を最大化、|T|-|Γ(T)|を最小化する点の集合S,Tを求められることを示す。
結論から言うと、最小カットc(A,B)にはU,V間の辺を通らないものが存在する(アルゴリズムデザイン335ページ参照)ので、その時S=A∩U,T=B∩Vとすればよい。
このとき|最小カット|=|A∩V|+|B∩U|=Γ(S)+|U|-|S|=|U|-(|S|-|Γ(S)|)となり、|U|が定数であることより示せた。
また|S|=|U|-|T|,|Γ(S)|=|V|-|Γ(T)|より|T|-|Γ(T)|が最小化されることも示せた。
あとはΓ(S)とTを点カバーの集合に使えば、最小の点でカバーできることがわかる。
ところで|Γ(S)|+|T|=|A∩V|+|B∩U|=|最小カット|=|最大マッチング|なので示せた。

int N;

int main() {
	while(scanf("%d", &N) != EOF) {
		int s = 2 * N, t = 2 * N + 1;
		MF::init(2 * N + 2);
		rep(i, 0, N) {
			int a, b;
			scanf("%d: (%d)", &a, &b);
			rep(j, 0, b) {
				int c; scanf("%d", &c);
				MF::add_edge(a, c + N, 1);
			}
			MF::add_edge(s, i, 1);
			MF::add_edge(i + N, t, 1);
		}
		printf("%lld\n", N - MF::get(s, t) / 2);
	}
	return 0;
}