题目链接:
题解:
对于A国,我们发现,最大团一定不大于2。对于B国,发现同奇偶性点之间都有边,不同奇偶性之间可能有边,也就是说对于B国是一个二分图最大团,也就是求B国补图的二分图最大独立集。然后,我们枚举使用A国的人员,将其与B国连接的点做一个补图,跑跑匈牙利即可。
【注】大视野上测试点和题面不一样啊!MMP没有t读入,只有一组数据,日哦!!
代码:
#include <cstdio>
#include <iostream>
#include <cstring> using namespace std; inline int read(){
int s=,k=;char ch=getchar();
while(ch<''|ch>'') ch=='-'?k=-:,ch=getchar();
while(ch>&ch<='') s=s*+(ch^),ch=getchar();
return s*k;
} const int N=3e3+; int A,B,M; struct edges{
int v;edges *last;
}edge[N*N],*head[N<<];int cnt; inline void push(int u,int v){
edge[++cnt]=(edges){v,head[u]};head[u]=edge+cnt;
} struct Country{
int sgl[N<<],cpl[N<<];
int cnt_sgl,cnt_cpl;
int val[N<<],re[N<<];
inline void add(int x,int pos){
if(x&){
sgl[++cnt_sgl]=pos;
val[pos]=x;re[pos]=cnt_sgl;
}else{
cpl[++cnt_cpl]=pos;
val[pos]=x;re[pos]=cnt_cpl;
}
}
inline void clear(){
cnt_sgl=cnt_cpl=;
}
}a,b; int f[N<<];bool vis[N<<]; inline bool find(int x){ for(edges *i=head[x];i;i=i->last){
if(!vis[i->v]){
vis[i->v]=true;
if(f[i->v]==-||find(f[i->v])){
f[i->v]=x;
return true;
}
}
}
return false;
} int v[][N<<],size[N<<],tt[N<<]; inline void build(){
for(int i=;i<=b.cnt_sgl;i++)
if(tt[b.sgl[i]]==){
for(int j=;j<=b.cnt_cpl;j++)
if(tt[b.cpl[j]]==){
int x=b.val[b.sgl[i]]|b.val[b.cpl[j]];
int t();
while(x) t+=x&,x>>=;
if((~t)&)
push(i,j);
}
}
} inline int solve(){
memset(f,-,sizeof(f));
int ret=;
for(int i=;i<=B;i++)
ret+=tt[i]==;
for(int i=;i<=b.cnt_sgl;i++){
if(tt[b.sgl[i]]==){
memset(vis,,sizeof(vis));
if(find(i))
ret--;
}
}
return ret;
} inline void clear(){
memset(head,,sizeof(head));
cnt=;
} int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
clear();
a.clear();b.clear();
memset(v,,sizeof(v));
memset(size,,sizeof(size));
A=read(),B=read(),M=read();
for(int i=;i<=A;i++) a.add(read(),i);
for(int i=;i<=B;i++) b.add(read(),i);
for(int i=,u,vv;i<=M;i++){
u=read(),vv=read();
v[u][++size[u]]=vv;
}
for(int i=;i<=B;i++)
tt[i]=;
build();
int ans=(a.cnt_sgl>)+(a.cnt_cpl>);
ans=max(ans,solve());
memset(tt,,sizeof(tt));
for(int i=;i<=a.cnt_sgl;i++){
for(int j=;j<=size[a.sgl[i]];j++)
tt[v[a.sgl[i]][j]]=;
clear();
build();
ans=max(ans,solve()+);
for(int j=;j<=size[a.sgl[i]];j++)
tt[v[a.sgl[i]][j]]=;
}
for(int j=;j<=a.cnt_cpl;j++){
for(int k=;k<=size[a.cpl[j]];k++)
tt[v[a.cpl[j]][k]]=;
clear();
build();
ans=max(ans,solve()+);
for(int k=;k<=size[a.cpl[j]];k++)
tt[v[a.cpl[j]][k]]=;
}
for(int i=;i<=a.cnt_sgl;i++){
for(int j=;j<=size[a.sgl[i]];j++)
tt[v[a.sgl[i]][j]]++;
for(int j=;j<=a.cnt_cpl;j++){
for(int k=;k<=size[a.cpl[j]];k++)
tt[v[a.cpl[j]][k]]++;
clear();
build();
ans=max(ans,solve()+);
for(int k=;k<=size[a.cpl[j]];k++)
tt[v[a.cpl[j]][k]]--;
}
for(int j=;j<=size[a.sgl[i]];j++)
tt[v[a.sgl[i]][j]]--;
}
printf("%d\n",ans); }