Description
在很久很久以前，曾经有两个国家和睦相处，无忧无虑的生活着。一年一度的评比大会开始了，作为和平的两国，一个朋友圈数量最多的永远都是最值得他人的尊敬，所以现在就是需要你求朋友圈的最大数目。两个国家看成是AB两国，现在是两个国家的描述：
1. A国：每个人都有一个友善值，当两个A国人的友善值a、b，如果a xor b mod 2=1，那么这两个人都是朋友，否则不是；
2. B国：每个人都有一个友善值，当两个B国人的友善值a、b，如果a xor b mod 2=0或者 (a or b)化成二进制有奇数个1，那么两个人是朋友，否则不是朋友；
3. A、B两国之间的人也有可能是朋友，数据中将会给出A、B之间“朋友”的情况。
4. 在AB两国，朋友圈的定义：一个朋友圈集合S，满足S∈A∪ B，对于所有的i，j∈ S ，i 和 j 是朋友
由于落后的古代，没有电脑这个也就成了每年最大的难题，而你能帮他们求出最大朋 友圈的人数吗？
Input
第一行输入三个整数A,B,M，表示A国人数、B国人数、AB两国之间是朋友的对数；第二行A个数ai，表示A国第i个人的友善值；第三行B个数bi，表示B国第j个人的友善值；第4——3+M行，每行两个整数（i，j），表示第i个A国人和第j个B国人是朋友。
Output
输出t行，每行，输出一个整数，表示最大朋友圈的数目。
Sample Input
2 4 7
1 2
2 6 5 4
1 1
1 2
1 3
2 1
2 2
2 3
2 4
Sample Output
5
【样例说明】
最大朋友圈包含A国第1、2人和B国第1、2、3人。
HINT
【数据范围】
两类数据
第一类：|A|<=200 |B| <= 200
第二类：|A| <= 10 |B| <= 3000
（HEOI原题还有测试数据组数，此题是每次测单组数据）
题解于代码注释中
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 3050
struct Syndra
{
int v,next;
}e[N*N];
int head[N],cnt;
int visit[N],crs[N],vov[N],vis[N];
int A,B,m,ans,n1,n2,num;
int a[N],b[N],s1[N],s2[N],map[N][N];
void add(int u,int v)//链式前向星加边
{
cnt++;
e[cnt].v=v;
e[cnt].next=head[u];
head[u]=cnt;
}
int dfs(int x)//匈牙利算法函数
{
int i,v;
for(i=head[x];i;i=e[i].next)
{
v=e[i].v;
if(!visit[v]&&!vis[v])
{//此处与模板略有不同
vis[v]=1;
if(!crs[v]||dfs(crs[v]))
{
crs[v]=x;
return 1;
}
}
}
return 0;
}
int main()
{
// freopen("test.in","r",stdin);
int i,j,k;
int i1,i2,j1;
int t,x,y;
scanf("%d%d%d",&A,&B,&m);
for(i=1;i<=A;i++)scanf("%d",&a[i]);
for(i=1;i<=B;i++)scanf("%d",&b[i]);
for(i=1;i<=A;i++)for(j=1;j<=B;j++)map[i][j]=1;
for(i=1;i<=m;i++)
{//map ：表示A、B两图之间点是否联通，1为有边 （反图）
scanf("%d%d",&x,&y);
map[x][y]=0;
}
for(i=1;i<=A;i++)
{//s1存奇数，s2存偶数（A图中点权）
if(a[i]&1)s1[++n1]=i;
else s2[++n2]=i;
}
for(i=1;i<=B;i++)
{//对B进行两两有序枚举，然后对B图进行建图
for(j=i+1;j<=B;j++)
{
if((b[i]&1)^(b[j]&1))
{
t=0;//两数|运算后二进制1的个数
for(k=0;(1LL<<k)<=(b[i]|b[j]);k++)
{
if((1LL<<k)&(b[i]|b[j]))t++;
}
if(!(t&1))add(i,j),add(j,i);
}
}
}
for(i=0;i<=n1;i++)
{
for(j=0;j<=n2;j++)
{
x=s1[i];
y=s2[j];
t=0;
memset(crs,0,sizeof(crs));
memset(visit,0,sizeof(visit));
for(k=1;k<=B;k++)
{
if(map[x][k]||map[y][k])
{//表示B图中j1这个点在当前枚举与A图联通
visit[k]=1;//k已被视为在最小覆盖中
t++;
}
}
for(k=1;k<=B;k++)
{//匈牙利算法求最大匹配
if((b[k]&1)&&(!visit[k]))
{//此处枚举b[k]为奇数偶数都行，但是本题数据偶数偏慢
memset(vis,0,sizeof(vis));
t+=dfs(k);
}
}
//A图中i，j是否存在，或者说能否录入答案
if(i)t--;
if(j)t--;
ans=max(ans,B-t);
}
}
printf("%d\n",ans);
return 0;
}