题目内容
洛谷链接
在很久很久以前，曾经有两个国家和睦相处，无忧无虑的生活着。
一年一度的评比大会开始了，作为和平的两国，一个朋友圈数量最多的永远都是最值得他人的尊敬，所以现在就是需要你求朋友圈的最大数目。两个国家看成是AB两国，现在是两个国家的描述：
(A)国：每个人都有一个友善值，当两个(A)国人的友善值(a,b)，如果(a ext{ xor} ext{ }b mod 2=1)，那么这两个人都是朋友，否则不是；
(B)国：每个人都有一个友善值，当两个(B)国人的友善值(a,b)，如果(a ext{ xor} ext{ }b mod 2=0)或者((a ext{ or} ext{ }b))化成二进制有奇数个(1)，那么两个人是朋友，否则不是朋友；
(A、B)两国之间的人也有可能是朋友，数据中将会给出(A、B)之间“朋友”的情况。 对于朋友的定义，关系是是双向的。 在AB两国，朋友圈的定义：一个朋友圈集合 (S)，满足(Ssubset A cup B)，对于所有的(i,j in S)，(i)和(j)是朋友。
由于落后的古代，没有电脑这个也就成了每年最大的难题，而你能帮他们求出最大朋友圈的人数吗？
输入格式
第一行一个整数(T(Tleq 6)),表示输入数据总数。
对于每组数据：
第一行三个整数 (A,B,M)，分别表示(A)国人数，(B)国人数，(AB)两国之间是朋友的对数。
第二行(A)个数(a_i)，表示A国第(i)个人的友善值。
第三行(B)个数(b_i)，表示B国第(i)个人的友善值。
第(4)到第(3+M)行，每行两个整数(x,y)表示(A)国的第(x)个人和(B)国第(y)个人是朋友。
输出格式
输出(T)行，每行输出一个整数，表示最大朋友圈的数目。
数据范围
友善值为int类型正整数。
有两类数据：
第一类：(|A| leq 200, |B| leq 200)；
第二类：(|A| leq 10, |B| leq 3000)。
样例输入
1
2 4 7
1 2
2 6 5 4
1 1
1 2
1 3
2 1
2 2
2 3
2 4
样例输出
5
最大朋友圈包含(A)国第(1,2)人和(B)国第(1,2,3)人。
思路
先吐槽：因为按位异或和按位与的优先级调这个破题一下午，谢谢有被恶心到。
此题一看就可知道是一个求最大团的问题，然而一般无向图的求最大团是一个(NPC)问题，况且看到其数据范围就可以弃了。所以我们要分析一下其中的性质。
先看(B)国，可以看出其为一些奇数点和偶数点，况且其中存在一些连边。是二分图既视感。不过二分图是两边的部点不存在连边，所以我们需要建一个关于(B)国的补图。同时补图的最大独立集就是原图的最大团，于是(B)国直接建补图跑最大独立集即可。
再看(A)国，其要求可理解为选出的人要求两两奇偶不同，所以(A)国只能选出(0、1、2)人，再看(B)国中和这几个人有关系的跑最大独立集，我们直接暴力把所有情况取个(max)即可，记得最大独立集(=n-)最大匹配数。
然后你快乐的连边之后一顿非常巨的操作跑匈牙利写完了发现(T)了几个点。（然后并不会(Dinic)），所以这时候就需要时间戳优化匈牙利。
匈牙利中占了时间效率很大的一块就是memset，每次都要memset理论每次都是(O(n))的效率（当然肯定要小一点），那么每匹配一次都是(O(n^2m))的，这个题要求多次匹配岂不是直接挂了。
所以时间戳优化出现了！其实根本没那么高深，设一个时间戳为( ext{Clock})，原来的布尔类型数组就改为整数类型，转化如下：
每次Clock++，即可(O(1))初始化。
然后就愉快的跑就完事了才不，这个毒瘤出题人居然卡常（可能只有我/kk），跑匈牙利的函数里的那个循环必须加register才能过（大数据居然快了( ext{200ms})），否则卡线(TLE)。
其他没啥了。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn=3000+10;
const int maxm=2e6+10;
int totA,totB,M,ans=-1;
int a[maxn],b[maxn];
bool g[maxn][maxn];
struct Edge{
int from,to,nxt;
}e[maxm];
inline int read(){
int x=0,fopt=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')fopt=-1;
ch=getchar();
}
while(isdigit(ch)){
x=(x<<3)+(x<<1)+ch-48;
ch=getchar();
}
return x*fopt;
}
int head[maxm],cnt;
inline void add(int u,int v){
e[++cnt].from=u;
e[cnt].to=v;
e[cnt].nxt=head[u];
head[u]=cnt;
}
int Time1,Time2;//时间戳，一个用于vis数组，一个用于标记朋友关系
int vis[maxn],match[maxn],flag[maxn];
bool dfs(int u){
for(register int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(vis[v]!=Time1&&flag[v]==Time2){
vis[v]=Time1;
if(!match[v]||dfs(match[v])){
match[v]=u;
return 1;
}
}
}
return 0;
}
inline int Count(int x){//数二进制1的个数
int res=0;
while(x){
if(x&1)res++;
x>>=1;
}
return res;
}
inline void SolveA(){
int sum=0;
for(int i=1;i<=totB;i++)
if(b[i]&1){
Time1++;
if(dfs(i))sum++;
}//选0个，直接对B跑匹配
ans=max(ans,totB-sum);
for(int i=1;i<=totA;i++){
int tot=0;sum=0;Time2++;
memset(match,0,sizeof(match));
for(int j=1;j<=totB;j++)
if(g[i][j+totA]){
flag[j]=Time2;tot++;//是朋友则flag[j]=1
}
for(int j=1;j<=totB;j++)
if((b[j]&1)&&flag[j]==Time2){
Time1++;
if(dfs(j))sum++;
}
ans=max(ans,tot-sum+1);//选1个，记得加上选的那个1
}
for(int i=1;i<=totA;i++)
for(int j=i+1;j<=totA;j++){
if((a[i]^a[j])&1){//记得打括号！调了一下午/kk
int tot=0;sum=0;Time2++;
memset(match,0,sizeof(match));
for(int k=1;k<=totB;k++)
if(g[i][k+totA]&&g[j][k+totA]){
flag[k]=Time2;tot++;
}
for(int k=1;k<=totB;k++)
if((b[k]&1)&&flag[k]==Time2){
Time1++;
if(dfs(k))sum++;
}
ans=max(ans,tot-sum+2);//同理，选2个
}
}
}
inline void SolveB(){
for(int i=1;i<=totB;i++)
if(b[i]&1){//建补图，即取条件不符合的
for(int j=1;j<=totB;j++){
if(!(b[j]&1)&&!(Count(b[i]|b[j])&1))
add(i,j);
}
}
}
int main(){
int T=read();
while(T--){
totA=read(),totB=read(),M=read();
for(int i=1;i<=totA;i++)
a[i]=read();
for(int i=1;i<=totB;i++)
b[i]=read();
SolveB();
for(int i=1;i<=M;i++){
int u=read(),v=read();
g[u][v+totA]=g[v+totA][u]=1;//记录朋友关系
}
SolveA();
printf("%d
",ans);
}
return 0;
}