HDU3829_Cat VS Dog

题目是这样的，给定一些人喜欢某只猫或者狗，讨厌某只猫或者狗。求最多能够同时满足多少人的愿望？

题目很有意思。建模后就很简单了。

对于同一只猫或者狗，如果有一个讨厌，另一个人喜欢，那么这两个连一条边。最终，最大独立集数等于最大匹配数就可以了。。

Orz。

召唤代码君：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

#define maxn 505

using namespace std;

vector<int> likec[maxn],disc[maxn],liked[maxn],disd[maxn];

vector<int> v[maxn];

int n,m,p,ans,t1,t2;

int f[maxn],tag[maxn];

char s1[maxn],s2[maxn];

void init()

{

	ans=0;

	for (int i=1; i<=p; i++) v[i].clear(),f[i]=0,tag[i]=0;

	for (int i=1; i<=n; i++) likec[i].clear(),disc[i].clear();

	for (int i=1; i<=m; i++) liked[i].clear(),disd[i].clear();

}

int num(char S[])

{

	int cur=0;

	for (int i=0; S[i]; i++) cur=cur*10+S[i]-'0';

	return cur;

}

int dfs(int cur,int T)

{

	if (tag[cur]==T) return false;

		else tag[cur]=T;

	for (unsigned i=0; i<v[cur].size(); i++)

	{

		if (tag[v[cur][i]]==T) continue;

		if (f[v[cur][i]]==0 || dfs(f[v[cur][i]],T))

		{

			f[v[cur][i]]=cur;

			f[cur]=v[cur][i];

			return true;

		}

	}

	return false;

}

int main()

{

	while (scanf("%d%d%d",&n,&m,&p)!=EOF)

	{

		init();

		for (int i=1; i<=p; i++)

		{

			scanf("%s%s",s1,s2);

			t1=num(s1+1),t2=num(s2+1);

			if (s1[0]=='C') likec[t1].push_back(i);

				else liked[t1].push_back(i);

			if (s2[0]=='C') disc[t2].push_back(i);

				else disd[t2].push_back(i);

		}

		for (int i=1; i<=n; i++)

			for (unsigned x1=0; x1<likec[i].size(); x1++)

				for (unsigned x2=0; x2<disc[i].size(); x2++)

				{

					v[likec[i][x1]].push_back(disc[i][x2]);

					v[disc[i][x2]].push_back(likec[i][x1]);

				}

		for (int i=1; i<=m; i++)

			for (unsigned x1=0; x1<liked[i].size(); x1++)

				for (unsigned x2=0; x2<disd[i].size(); x2++)

				{

					v[liked[i][x1]].push_back(disd[i][x2]);

					v[disd[i][x2]].push_back(liked[i][x1]);

				}

		for (int i=1; i<=p; i++)

		{

			if (f[i]!=0) continue;

			if (dfs(i,i)) ans++;

		}

		printf("%d\n",p-ans);

	}

	return 0;

}