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

本文主要是介绍【二分图最大独立集】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));//这里每次都需要全部清0if(Find(i))ans++;}printf("Case %d: %d\n",c,n+m-ans);}return 0;
}