Description：

有两个国家， $A$ 国人之间是朋友当且仅当他们的友善值异或为 $1$ ， $B$ 国的人之间是朋友当且仅当他们友善值的异或值为 $1$ 或他们友善值或起来有奇数个 $1$ ，求最大的集合 $S$ 满足 $S\subset A\cap B$ ， $\forall i,j\in S$ 有 $i$ 和 $j$ 是朋友。

两类数据

第一类： $|A|\le200$ $|B| \le 200$

第二类： $|A| \le 10$ $|B| \le 3000$

Solution：

把朋友看成边，则 $A$ 国是一个二分图， $B$ 国的点可以分成两部分，两部分之内是一个完全图，之间有一些边， $A$ 国和 $B$ 国之间有一些边，求最大团。最大团并不好求，一般做法是取补图求最大独立集，发现 $A$ 国中只能取两个，一个奇数一个偶数，不妨枚举这两个人，在补图中删掉与这两个人相连的 $B$ 国人， $B$ 国人取补图之后也是一个二分图，求这个二分图的最大独立集即可。

由于本来 $A$ 和 $B$ 之间的边就不多，所以取补图之后可以删掉绝大部分点，算法的瓶颈变成了每次循环的 $memset$ ，于是打时间戳即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int read()

{

	int res = 0;

	char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int na,nb,m;

#define MAXNA 210

#define MAXNB 3010

int a[MAXNA],b[MAXNB];

bool g[MAXNA][MAXNB];

int cnt1 = 0,cnt2 = 0;

int tag[MAXNB],vis1[MAXNB];

int match[MAXNB];

struct edge

{

	int to,nxt;

}e[MAXNB * MAXNB];

int lin[MAXNB] = {0};

int edgenum = 0;

void add(int a,int b)

{

	++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

bool find(int k)

{

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(tag[e[i].to] != cnt1 && vis1[e[i].to] != cnt2)

		{

			vis1[e[i].to] = cnt2;

			if(match[e[i].to] == -1 || find(match[e[i].to]))

			{

				match[e[i].to] = k;

				return true;

			}

		}

	}

	return false;

}

int query(int x = 0,int y = 0)

{

	int ans = 0;

	++cnt1;

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

		if(g[x][i] || g[y][i])

		{

			++ans;

			tag[i] = cnt1;

		}

	memset(match,-1,sizeof(match));

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

	{

		if(b[i] & 1 && tag[i] != cnt1)

		{

			++cnt2;

			if(find(i))++ans;

		}

	}//cout  << nb - ans << " ";

	return nb - ans;

}

void solve()

{

	int ans = query();

	for(int i = 1;i <= na;++i)ans = max(ans,query(i) + 1);

	for(int i = 1;i <= na;++i)if(a[i] & 1)

	for(int j = 1;j <= na;++j)if(!(a[j] & 1))

			ans = max(ans,query(i,j) + 2);

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

	return;

}

int calc(int a)

{

	int cnt = 0;

	while(a > 0)

	{

		++cnt;

		a -= (a & (-a));

	}

	return cnt;

}

void work()

{

	scanf("%d%d%d",&na,&nb,&m);

	for(int i = 1;i <= na;++i)a[i] = read();

	for(int i = 1;i <= nb;++i)b[i] = read();

	int x,y;

	memset(g,true,sizeof(g));

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

	{

		x = read();y = read();

		g[x][y] = false;

	}

	for(int i = 1;i <= nb;++i)g[0][i] = false;

	for(int i = 1;i <= nb;++i)if((b[i] & 1) == 0)

	for(int j = 1;j <= nb;++j)if((b[j] & 1) == 1)

		if((calc(b[i] | b[j]) & 1) == 0)

			add(i,j);

	solve();

	return;

}

int main()

{

	work();

	return 0;

}