记录编号	376453	评测结果	AAAAAAAAAA
题目名称	2620.[HEOI 2012]朋友圈	最终得分	100
用户昵称	小一米	是否通过	通过
代码语言	C++	运行时间	0.524 s
提交时间	2017-02-27 11:37:39	内存使用	8.63 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
int T,A,B,M,tim;
int a[205],b[3005],last[3005];
bool not_friend[3005][3005],ok[205][3005];
int belong[3005];
bool vis[3005];
namespace Hungary
{
	vector<int>e[3005];
	
	bool find(int x)
	{
		for (int i=0;i<e[x].size();++i)
			if (!vis[e[x][i]]&&last[e[x][i]]==tim)
			{
				vis[e[x][i]]=1;
				if (!belong[e[x][i]]||find(e[x][i]))
				{
					belong[e[x][i]]=x;
					belong[x]=e[x][i];
					return 1;
				}
			}
		return 0;
	}
}
main()
{
	freopen("friends.in","r",stdin);
	freopen("friends.out","w",stdout);
	scanf("%d",&T);
	scanf("%d%d%d",&A,&B,&M);
	for (int i=1;i<=A;++i) scanf("%d",a+i);
	for (int i=1;i<=B;++i) scanf("%d",b+i),last[i]=1;
	for (int u,v,i=1;i<=M;++i)
		scanf("%d%d",&u,&v),
		ok[u][v]=1;
	int tmp,num;
	for (int i=1;i<=B;++i)
		for (int j=1;j<i;++j)
		if ((b[i]^b[j])&1)
		{
			tmp=(b[i]|b[j]);
			num=0;
			for (;tmp;tmp^=tmp&-tmp) ++num;
			if (num&1);
			else Hungary::e[i].push_back(j),Hungary::e[j].push_back(i);
		}
	tim=1;
	int ans=0;
	for (int i=1;i<=B;++i)
	{
		if (!vis[i]) Hungary::find(i);
		if (belong[i]&&(b[i]&1)) ++ans;
	}
	ans=B-ans;
//	printf("%d\n",ans); 
	int sum;
	for (int i=1;i<=A;++i)
	{
		++tim;
		sum=1;
		for (int j=1;j<=B;++j)
		{
			vis[j]=0;belong[j]=0;
			if (ok[i][j])
				++sum,
				last[j]=tim;
		}
		for (int j=1;j<=B;++j)
		if (last[j]==tim)
		{
			if (!vis[j]) Hungary::find(j);
			if (belong[j]&&(b[j]&1)) --sum; 
		}
		ans=max(sum,ans);
	}
	for (int i=1;i<=A;++i)
		for (int j=i+1;j<=A;++j)
		if ((a[i]^a[j])&1)
		{
			++tim;
			sum=2;
			for (int k=1;k<=B;++k)
			{
				vis[k]=0;belong[k]=0;
				if (ok[i][k]&&ok[j][k])
					++sum,
					last[k]=tim;
			}
			for (int k=1;k<=B;++k)
			if (last[k]==tim)
			{
				if (!vis[k]) Hungary::find(k);
				if (belong[k]&&(b[k]&1)) --sum; 
			}
//			if (sum==11) {printf("%d %d\n",i,j);return 0;}
			ans=max(sum,ans);
		}
	printf("%d\n",ans); 
}