http://poj.org/problem?id=3692
男女がお互いを知っている最大の集合を求める。
これは男女がお互いを知らない、ということはない最大の集合であるので、
知り合いではない男女を辺でつないで最大安定集合を求めれば良い。
あとは|最大安定集合|=V-|最大マッチング|でできる。
最大安定集合はなんていうか否定が絡むイメージ。
bool V[MAX_N][MAX_N]; int N, M, G; int main() { for(int q = 1; ; q++) { scanf("%d%d%d", &N, &M, &G); if(N == 0 && M == 0 && G == 0) break; memset(V, 0, sizeof(V)); MF::init(N + M + 2); rep(i, 0, G) { int a, b; scanf("%d%d", &a, &b); a--; b--; V[a][b + N] = true; } int s = N + M, t = N + M + 1; rep(i, 0, N) { rep(j, N, M + N) { if(!V[i][j]) MF::add_edge(i, j, 1); } } rep(i, 0, N) MF::add_edge(s, i, 1); rep(i, 0, M) MF::add_edge(i + N, t, 1); printf("Case %d: %lld\n", q, N + M - MF::get(s, t)); } return 0; }
Kindergardenのミススペルだと思ったら、Kindergartenの方が正しかった…