HDU - 3829 Cat VS Dog （二分匹配）

你的名字 2022-05-17 12:37 97阅读 0赞

#                                              Cat VS Dog #

### Problem Description ###

The zoo have N cats and M dogs, today there are P children visiting the zoo, each child has a like-animal and a dislike-animal, if the child's like-animal is a cat, then his/hers dislike-animal must be a dog, and vice versa.  
Now the zoo administrator is removing some animals, if one child's like-animal is not removed and his/hers dislike-animal is removed, he/she will be happy. So the administrator wants to know which animals he should remove to make maximum number of happy children.

### Input ###

The input file contains multiple test cases, for each case, the first line contains three integers N <= 100, M <= 100 and P <= 500.  
Next P lines, each line contains a child's like-animal and dislike-animal, C for cat and D for dog. (See sample for details)

### Output ###

For each case, output a single integer: the maximum number of happy children.

### Sample Input ###

1 1 2

C1 D1

D1 C1

1 2 4

C1 D1

C1 D2

D2 C1

### Sample Output ###

### *Hint* ###

Case 2: Remove D1 and D2, that makes child 1, 2, 3 happy.

**题意描述：**

给出猫的个数和狗的个数，及每个小朋友喜欢和讨厌的动物，去哪个小朋友讨厌的动物哪个小朋友就会高兴起来并且不能同时去掉他喜欢的动物，求最多可以是几个小朋友高兴。

**解题思路：**

将小朋友喜欢的动物和别人讨厌的动物相同的两个小朋友建立边，因从头到尾将小朋友查找了一边所以会建成一个双向边，用二分匹配查找出最大独立集即为使小朋友高兴的最多数量。注意因为建的是双向图，所以小朋友的数量减去最大匹配数的一半才是最大独立集。

#include<stdio.h>
    #include<string.h>
    int e[510][510],book[510],match[510];
    int n;
    int dfs(int u)
    {
    	int i;
    	for(i=1;i<=n;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 i,j,c,d,sum;
    	char  s1[510][5],s2[510][5];
    	while(scanf("%d%d%d",&c,&d,&n)!=EOF)
    	{
    		memset(match,0,sizeof(match));
    		memset(e,0,sizeof(e));
    		for(i=1;i<=n;i++)
    			scanf("%s%s",s1[i],s2[i]);
    		for(i=1;i<=n;i++)
    			for(j=1;j<=n;j++)
    				if(strcmp(s1[i],s2[j])==0||strcmp(s1[j],s2[i])==0)
    					e[i][j]=1;
    		sum=0;
    		for(i=1;i<=n;i++)
    		{
    			memset(book,0,sizeof(book));
    			if(dfs(i))
    				sum++;
    		}
    		printf("%d\n",n-(sum/2));
    	}
    	return 0;
    }