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

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
#define inf 1e9
using namespace std;
int T,A,B,M;
int a[205],b[3005],X[3005],Y[3005];
bool ok[205][3005],not_friend[3005][3005];
int belong[3005],vis[3005];
namespace network
{
	int s,t,tot,first[3005],dis[3005];
	queue<int>q;
	struct edge{
		int v,w,next;
	}e[6000005];
	void init()
	{
		memset(first,0,sizeof(first));
		tot=1;s=0;t=B+1;
	}
	void add(int x,int y,int z)
	{
		e[++tot].v=y;e[tot].w=z;e[tot].next=first[x];first[x]=tot;
		e[++tot].v=x;e[tot].w=0;e[tot].next=first[y];first[y]=tot;
	}
	bool bfs()
	{
		memset(dis,0,sizeof(dis));
		int x;
		dis[s]=1;
		for (q.push(s);!q.empty();q.pop())
		{
			x=q.front();
			for (int i=first[x];i;i=e[i].next)
				if (!dis[e[i].v]&&e[i].w)
					dis[e[i].v]=dis[x]+1,
					q.push(e[i].v);
		}
		return dis[t]>0;
	}
	int dfs(int x,int maxn)
	{
		if (x==t) return maxn;
		int used=0,k;
		for (int i=first[x];i;i=e[i].next)
			if (dis[e[i].v]==dis[x]+1)
			{
				k=dfs(e[i].v,min(maxn-used,e[i].w));
				e[i].w-=k;e[i^1].w+=k;
				used+=k;
				if (used==maxn) return maxn;
			}
		if (!used) dis[x]=0;
		return used;
	}
}
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);
	for (int u,v,i=1;i<=M;++i)
		scanf("%d%d",&u,&v),
		ok[u][v]=1;
	network::init();
	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 not_friend[i][j]=not_friend[j][i]=1;
		}
		if (b[i]&1) X[++X[0]]=i,network::add(network::s,i,1);
		else Y[++Y[0]]=i,network::add(i,network::t,1);
	}
	for (int i=1;i<=X[0];++i)
		for (int j=1;j<=Y[0];++j)
			if (not_friend[X[i]][Y[j]])
				network::add(X[i],Y[j],1);
	int ans=B;
	while (network::bfs()) ans-=network::dfs(network::s,inf);
	int sum;
	for (int i=1;i<=A;++i)
	{
		X[0]=Y[0]=0;
		network::init();
		for (int j=1;j<=B;++j)
		{
			belong[j]=0;
			if (ok[i][j])
				if (b[j]&1) X[++X[0]]=j,network::add(network::s,j,1);
				else Y[++Y[0]]=j,network::add(j,network::t,1);
		}
		sum=X[0]+Y[0]+1;
		for (int j=1;j<=X[0];++j)
			for (int k=1;k<=Y[0];++k)
				if (not_friend[X[j]][Y[k]]) network::add(X[j],Y[k],1);
		while (network::bfs()) sum-=network::dfs(network::s,inf);
		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)
		{
			X[0]=Y[0]=0;
			network::init();
			for (int k=1;k<=B;++k)
			{
				belong[k]=0;
				if (ok[i][k]&&ok[j][k])
					if (b[k]&1) X[++X[0]]=k,network::add(network::s,k,1);
					else Y[++Y[0]]=k,network::add(k,network::t,1);
			}
			sum=X[0]+Y[0]+2;
			for (int k=1;k<=X[0];++k)
				for (int l=1;l<=Y[0];++l)
					if (not_friend[X[k]][Y[l]]) network::add(X[k],Y[l],1);
			while (network::bfs()) sum-=network::dfs(network::s,inf);
			ans=max(sum,ans);
		}
	printf("%d\n",ans); 
}