Kindergarten
题意：
- 有一堆小朋友，男孩子都相互认识，女孩子也都相互认识。有些女孩子认识一些男孩子。输出最大的人数使得这些孩子都相互认识。
思路：
- 最大点独立集是点集中没有直接相连的边。而题目给的是认识的连线，求出的最大点独立集将会是两两之间全都不认识的集合。
- 想要求出最大认识的集合，可以将认识人的图转化成补图。两者有连线的都是陌生的。找出来的最大点独立集就不是没有这种陌生关系的最大人数吗？没有陌生关系那不就是认识吗
哈哈哈哈哈- 由于只有一些男生与一些女生不认识，那么将这些人进行连线(有连线的代表不认识)然后对图进行最大点独立集(尽可能多的点两点之间没有直接相连的边)找出来的最大独立集就是都认识的人最大个数了
- 最大点独立集是点集中任何两点都没有直接相互连接的边。以为这原图的这个集合中任何人都没有直接相连的边，意味着这个集合中的人全部都相互认识
最大点独立集==总点数-最大边匹配
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int edge[210][210];
int match[210];
int vis[210];
int n,m;
int Hungarian(int x)
{
for(int i=1;i<=m;i++)
{
if(!vis[i]&&edge[x][i])
{
vis[i]=1;
if(match[i]==-1||Hungarian(match[i]))
{
match[i]=x;
return 1;
}
}
}
return 0;
}
int main( )
{
int k,x,y;
int t=0;
while(~scanf("%d%d%d",&n,&m,&k)&&(n+m+k))
{
t++;
memset(edge,1,sizeof(edge));//建立补图
memset(match,-1,sizeof(match));
for(int i=1;i<=k;i++)
{
scanf("%d%d",&x,&y);
edge[x][y]=0;//认识为0
}
int ans=0;
for(int i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
if(Hungarian(i))
{
ans++;
}
}
printf("Case %d: %d\n",t,m+n-ans);
}
return 0;
}
