POJ 3692 Kindergarten

POJ 3692 Kindergarten

• POJ 3692
• 已知班级有G个女孩和B个男孩，所有女生之间都相互认识，所有 男生之间也相互认识，给出M对关系表示哪个女孩与哪个男孩认 识。现在要选择一些学生来组成一个团，使得里面所有人都认识， 求此团最大人数
• G, B <= 200

分析：题目中要求二分图能组成的最大团，就等于原图补图的独立集。而独立集也就是顶点减去最大匹配数。配合模板使用效果奇佳。
附AC代码：

#include<iostream>
#include<cstdio>
#include<string.h>
#include<algorithm>
#include<fstream>
using namespace std;
const int SIZE = 220;
int line[SIZE][SIZE];
bool used[SIZE];
int n,m,k;
int all;
int i ,j;
int boy[SIZE];
bool find(int x){int i,j;for (j=1;j<=m;j++){if (line[x][j]==false && used[j]==false)      {used[j]=1;if (boy[j]==0 || find(boy[j])) { boy[j]=x;return true;}}}return false;
}
void ini()
{all =0;memset(boy,0,sizeof(boy));memset(line,0,sizeof(line));
}int main()
{int t=0;while(cin>>n>>m>>k){if(n==0&&m==0&&k==0)break;ini();for(i=0; i<k;i++){int x,y;cin>>x>>y;line[x][y] = true;}for (i=1;i<=n;i++){   memset(used,0,sizeof(used));    if (find(i) )all+=1;    }//cout<<"all"<<all<<endl;printf("Case %d: %dn",++t,max(max(m+n-all,m),n)); }return 0; 
}