POJ 3692 Kindergarten(最大独立集)
http://poj.org/problem?id=3692
题意:
已知班级有g个女孩和b个男孩,所有女生之间都相互认识,所有男生之间也相互认识,给出m对关系表示哪个女孩与哪个男孩认识。现在要选择一些学生来组成一个团,使得里面所有人都认识,求此团最大人数。
分析:
任意两个同学之间要么认识,要么不认识.现在我们根据所有同学之间的不认识关系来建图.
假设女生在左边点集,男生在右边点集.那么左边点集的内部肯定没边,右边点集同样没边. 对于女生i与男生j不认识的话,就连一条左边i与右边j的无向边. 这个图肯定是二分图.
然后我们现在要在这个图中选择最多的点,使得所选点集合中任意两个点都不存在边.(不存在边,那么就是任意两点都相互认识.其实就是该图的最大独立集).
由于最大独立集 = n(图节点总数)-最小覆盖数=n-最大匹配数. 所以我们只要求除最大匹配数即可.
AC代码:
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn= 200+5;
struct Max_Match
{
int n, m;
bool g[maxn][maxn];
bool vis[maxn];
int left[maxn];
void init(int n, int m)
{
this->n = n;
this->m = m;
for(int i = 1; i <= n; i++)
for(int j=1;j<=m;j++)
g[i][j]=true;
memset(left,-1,sizeof(left));
}
bool match(int u)
{
for(int v=1;v<=m;v++)if(g[u][v] && !vis[v])
{
vis[v]=true;
if(left[v]==-1 || match(left[v]))
{
left[v]=u;
return true;
}
}
return false;
}
int solve()
{
int ans=0;
for(int i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
if(match(i)) ans++;
}
return ans;
}
}MM;
int main()
{
int n,m,k,kase=0;
while(scanf("%d%d%d",&n,&m,&k)==3&&n)
{
MM.init(n,m);
while(k--)
{
int u,v;
scanf("%d%d",&u,&v);
MM.g[u][v]=false;
}
printf("Case %d: %d\n",++kase,n+m-MM.solve());
}
return 0;
}
分享到:
相关推荐
POJ 1988 并查集。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj2492 A Bug's Life并查集应用的扩展,希望可以给大家带来用处
poj openjudge 1111题最大正向匹配 提交ac
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
西北工业大学POJ作业100份源代码. 每个人的poj顺序是不一样的, 不过还是有参考价值的.
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
poj 1611 The Suspects 代码 并查集的应用
POJ1048,加强版的约瑟夫问题 难度中等
北大POJ2002-Squares 解题报告+AC代码