记录编号	294392	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]猫和狗	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.013 s
提交时间	2016-08-12 06:14:52	内存使用	2.25 MiB

#include<cstdio>
const int maxn=505;
int like[maxn],dislike[maxn],typ[maxn];
struct edge{
	int to,next;
}lst[maxn*maxn];int len=1;
int first[maxn];
void addedge(int a,int b){
	lst[len].to=b;
	lst[len].next=first[a];
	first[a]=len++;
}
int T;int vis[maxn],match[maxn];
bool dfs(int x){
	for(int pt=first[x];pt;pt=lst[pt].next){
		if(vis[lst[pt].to]!=T){
			vis[lst[pt].to]=T;
			if(!match[lst[pt].to]||dfs(match[lst[pt].to])){
				match[lst[pt].to]=x;//match[x]=lst[pt].to;
				return true;
			}
		}
	}
	return false;
}
int main(){
	freopen("catdog.in","r",stdin);
	freopen("catdog.out","w",stdout);
	int ncat,ndog,nhuman;
	scanf("%d %d %d",&ncat,&ndog,&nhuman);
	char buf1[10],buf2[10];int x,y;
	for(int i=1;i<=nhuman;++i){
		scanf("%s %s",buf1,buf2);
		x=0;y=0;
		for(int j=1;buf1[j]!='\0';++j)x=x*10+buf1[j]-'0';
		for(int j=1;buf2[j]!='\0';++j)y=y*10+buf2[j]-'0';
		if(buf1[0]=='C'){typ[i]=2;
			like[i]=x;
			dislike[i]=ncat+y;
		}
		else{typ[i]=1;
			like[i]=ncat+x;
			dislike[i]=y;
		}
	}
	for(int i=1;i<=nhuman;++i){
		for(int j=i+1;j<=nhuman;++j){
			if(typ[i]==typ[j])continue;
			if(like[i]==dislike[j]||like[j]==dislike[i]){
				addedge(i,j);addedge(j,i);
			}
		}
	}
	int ans=0;
	for(int i=1;i<=nhuman;++i){
		if(typ[i]==2)continue;
		vis[i]=++T;
		if(!match[i]&&dfs(i)){
			ans++;
		}
	}
	printf("%d\n",nhuman-ans);
	fclose(stdin);fclose(stdout);
	return 0;
}