手捏了好几个数据都 hack 不掉我的程序,第一个点到底是什么数据......
#include<bits/stdc++.h>
#define N 3005
#define M 400005
#define inf 0x3f3f3f3f
#define II inline int
#define IV inline void
#define re read()
#define pf printf
#define gc getchar()
#define pfi(x) printf("%d\n",x)
#define cmx(x,y) x=max(x,y)
#define clr(a,n) memset(a,0,sizeof(int)*(n))
#define cpy(f,g,n) memcpy(f,g,sizeof(int)*(n))
#define f(i,x,y) for(int i=(x); i<=(y); i++)
#define fe(i,v,u) for(int i=head[u],v=e[i].v; i; i=e[i].nex,v=e[i].v)
using namespace std;
II read(){
int res=0; char c=gc;
while(c<48 || 57<c) c=gc;
while(47<c && c<58) res=(res<<1)+(res<<3)+(c^48),c=gc;
return res;
}
int n0,n1,m,s,t,ans;
int a[N],b[N];
struct edge{
int v,w,nex;
}e[N*N<<1];
int sav[N],head[N],now[N],cnt;
IV adde(int u,int v,int w){
e[++cnt]={v,w,head[u]}; head[u]=cnt;
e[++cnt]={u,0,head[v]}; head[v]=cnt;
}
queue<int>q;
int d[N];
bool bfs(){
clr(d,t+1);
while(!q.empty()) q.pop();
q.push(s); d[s]=1; now[s]=head[s];
int u;
while(!q.empty()){
u=q.front(); q.pop();
fe(i,v,u)
if(e[i].w && !d[v]){
q.push(v);
now[v]=head[v];
d[v]=d[u]+1;
if(v==t) return 1;
}
}
return 0;
}
II dinic(int u,int fl){
if(u==t) return fl;
int res=fl,k,i,v;
for(i=now[u]; i; i=e[i].nex)
if(e[i].w && d[u]+1==d[v=e[i].v]){
k=dinic(v,min(res,e[i].w));
if(!k) d[v]=0;
e[i].w-=k; e[i^1].w+=k;
res-=k;
if(res==0) break;
}
now[u]=i;
return fl-res;
}
int in[N];
vector<int>ev[N];
int pc[N][N];
II calc(int x,int y){
clr(in,t+1); clr(head,t+1); cnt=1;
int o=(x>0)+(y>0),tot=0;
for(int v:ev[x]) in[v]++;
for(int v:ev[y]) in[v]++;
f(i,1,n1) if(in[i]==o){
tot++;
if(b[i]&1){
adde(s,i,1);
f(j,1,n1) if(in[j]==o && !(b[j]&1) && !(pc[i][j]&1)) adde(i,j,1);
}
else adde(i,t,1);
}
int res=0;
while(bfs()) res+=dinic(s,inf);
return o+tot-res;
}
IV sol(){
s=n1+1; t=s+1;
f(i,1,n1)
f(j,1,n1) pc[i][j]=__builtin_popcount(b[i]|b[j]);
cmx(ans,calc(0,0));
f(i,0,n0)
f(j,i+1,n0) cmx(ans,calc(i,j));
pfi(ans);
}
signed main(){
int T=re;
while(T--){
n0=re; n1=re; m=re;
ans=0;
f(i,1,n0) ev[i].clear();
f(i,1,n0) a[i]=re;
f(i,1,n1) b[i]=re;
int u,v;
f(i,1,m) u=re,v=re,ev[u].push_back(v);
sol();
}
return 0;
}