• 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: %d\n",++t,max(max(m+n-all,m),n)); } return 0; }