POJ - 3692 Kindergarten（二分匹配）

曾经终败给现在 2022-05-17 12:37 132阅读 0赞

#                                           Kindergarten #

### Description ###

In a kindergarten, there are a lot of kids. All girls of the kids know each other and all boys also know each other. In addition to that, some girls and boys know each other. Now the teachers want to pick some kids to play a game, which need that all players know each other. You are to help to find maximum number of kids the teacher can pick.

### Input ###

The input consists of multiple test cases. Each test case starts with a line containing three integers  
*G*, *B* (1 ≤ *G*, *B* ≤ 200) and *M* (0 ≤ *M* ≤ *G* × *B*), which is the number of girls, the number of boys and  
the number of pairs of girl and boy who know each other, respectively.  
Each of the following *M* lines contains two integers *X* and *Y* (1 ≤ *X*≤ G,1 ≤ *Y* ≤ B), which indicates that girl X and boy Y know each other.  
The girls are numbered from 1 to *G* and the boys are numbered from 1 to *B*.

The last test case is followed by a line containing three zeros.

### Output ###

For each test case, print a line containing the test case number( beginning with 1) followed by a integer which is the maximum number of kids the teacher can pick.

### Sample Input ###

2 3 3
    1 1
    1 2
    2 3
    2 3 5
    1 1
    1 2
    2 1
    2 2
    2 3
    0 0 0

### Sample Output ###

Case 1: 3
    Case 2: 4

**题意描述：**  
有G个女生B个男生，女生间相互认识，男生间相互认识，现在给出m组男女生间相互认识的，女生x认识男生y，找出所有的人都相互认识的人，最多能找多少。

**解题思路：**  
与一般的存二分图不同，因为此时的男生女生他们同性间是相互认识的也就是他们之间是有边的，所以存图的时候可以进行反着存将e输出初始化为1，关注不相互认识的人，相互认识的不连边，若两个人相互认识，e数组赋值为0，利用二分匹配求出最大独立集，得到的就是所有相互了解的最大人数了。

#include<stdio.h>
    #include<string.h>
    int e[210][210],book[210],match[210];
    int G,B;
    int dfs(int u)
    {
    	int i;
    	for(i=1;i<=B;i++)
    	{
    		if(book[i]==0&&e[u][i]==1)
    		{
    			book[i]=1;
    			if(match[i]==0||dfs(match[i]))
    			{
    				match[i]=u;
    				return 1;
    			}
    		}
    	}
    	return 0;
    }
    int main()
    {
    	int M,i,j,sum,a,b,s=0,flag;
    	while(scanf("%d%d%d",&G,&B,&M))
    	{
    		if(G==0&&B==0&&M==0)
    			break;
    		s++;
    		for(i=1;i<=G;i++)
    			for(j=1;j<=B;j++)
    				e[i][j]=1;
    		memset(match,0,sizeof(match));
    		for(i=1;i<=M;i++)
    		{
    			scanf("%d%d",&a,&b);
    			e[a][b]=0;
    		}
    		sum=0;
    		for(i=1;i<=G;i++)
    		{
    			memset(book,0,sizeof(book));
    			if(dfs(i))
    				sum++;
    		}
    		printf("Case %d: ",s);
    			printf("%d\n",G+B-sum);
    	}
    	return 0;
    }