【二分图最大独立集】POJ 3692：Kindergarten

一、题目内容

POJ 3692 原题地址

二、题意解释

一群男孩女孩，同性之间都相互认识，但是异性之间只有某些人认识彼此。给出相互认识的异性的各自编号。 求组成一个小队，这个小队里的人都相互认识。问这个小队最多能有多少人。

三、代码及注释

#include<stdio.h> #include<iostream> #include<string.h> using namespace std; /* 把相互不了解的人作为边构建二分图，这样题意是选择相互了解的人，那么是选择二分图的最大独立集，即总端点数-最大匹配（最小点覆盖） */ const int maxn=205; int g[maxn][maxn]; int girl[maxn],used[maxn];//girl表示女生喜欢的男生，used表示女生是否被匹配到 int n,m,e; bool Find(int x) { for (int i = 1; i <= m; i++) // n 为女生的个数，这道题和男生个数一样 { if (g[x][i] && !used[i]) // x 和 i 是互相喜欢的，并且这个妹子名花无主 { used[i] = 1;// 表示这个妹子配对上 if (girl[i] == 0 || Find(girl[i])) { // 如果这个妹子没有匹配上人 或者 这个男生可以喜欢别人 girl[i] = x;// i 个女生就和 x 配对上 return true; } } } return false; } int main() { int c=0; while(scanf("%d%d%d",&n,&m,&e)!=EOF) { c++; if(n==0&&m==0&&e==0) break; memset(girl, 0, sizeof(girl)); memset(g, 1, sizeof(g)); while(e--) { int c,r; scanf("%d%d",&c,&r); g[c][r]=0; } int ans=0; for(int i=1; i<=n; i++) //枚举集合A中的点，n为集合A中点的个数，即男生的个数 { memset(used,0,sizeof(used));//这里每次都需要全部清0 if(Find(i))ans++; } printf("Case %d: %d\n",c,n+m-ans); } return 0; }