学步园

这个题，因为只有两个集合，很容易让人想到二分图最大匹配

所以我们把喜欢猫和喜欢狗的人分为两个集合。

然后如果A君喜欢B君讨厌的，或者A君讨厌B君喜欢的

那么就把A君和B君之间连一条边。

然后再求一个最大独立集，就是答案了。

我的代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>

using namespace std;

struct node
{
	char like[5];
	char dislike[5];
};
node cater[505],doger[505];
int n,m,p;
int num1,num2;
int used[505];
bool map[505][505];
int link[505];

bool dfs(int u)
{
	int i;
	for(i=1;i<=num2;i++)
	{
		if(map[u][i]&&!used[i])
		{
			used[i]=true;
			if(link[i]==-1||dfs(link[i]))
			{
				link[i]=u;
				return true;
			}
		}
	}
	return false;
}

int main()
{
	int i,j,ans;
	char s1[5],s2[5];
	while(scanf("%d%d%d",&n,&m,&p)!=EOF)
	{
		num1=0,num2=0,ans=0;
		memset(map,0,sizeof(map));
		memset(link,-1,sizeof(link));
		for(i=1;i<=p;i++)
		{
			scanf("%s%s",s1,s2);
			if(s1[0]=='C')
			{
				num1++;
				strcpy(cater[num1].like,s1);
				strcpy(cater[num1].dislike,s2);
			}
			if(s1[0]=='D')
			{
				num2++;
				strcpy(doger[num2].like,s1);
				strcpy(doger[num2].dislike,s2);
			}
		}
		for(i=1;i<=num1;i++)
			for(j=1;j<=num2;j++)
			{
				if(strcmp(cater[i].like,doger[j].dislike)==0||strcmp(cater[i].dislike,doger[j].like)==0)
					map[i][j]=true;
			}
		for(i=1;i<=num1;i++)
		{
			memset(used,0,sizeof(used));
			if(dfs(i))
				ans++;
		}
		printf("%d\n",p-ans);
	}
	return 0;
}