题目

我们发现我们要求的是一个最大团问题，众所周知这是一个\(NP\)难问题，除了爆搜没有什么别的方法，但是这道题我们可以根据图的特殊性质入手

我们如果把\(B\)国的人分成奇数和偶数两类，就会发现奇数和偶数这两部分都是一个团

而且这两部分之间有一些连边

很像二分图是吧，就只是左右两边的点从两两没边变成了两两有边

于是我们取一个补图，这张图就变成了一张二分图

补图有一个非常好的性质，补图最大独立集等于原图最大团

这个很好理解吗，最大团要求两两有边，最大独立集要求两两没边，于是把边的存在性取反之后两者是等价的

而二分图的最大独立集等于总点数-最小点覆盖

最小点覆盖等于最大匹配

于是\(B\)国的情况我们就解决了

再来看看\(A\)国和跨国关系

发现\(A\)国中只能选择\(0,1,2\)人，于是我们枚举在\(A\)国里选择哪些人，之后处理出\(B\)国中的和这些人都有朋友关系的人，对这些点跑最大独立集就好了

之后就是如何跑最大匹配的问题了，发现全网都是时间戳优化的匈牙利

毕竟匈牙利不用每次都重构图

但是我\(Dinic\)不服！

只要控制好数组的大小，\(Dinic\)也是能跑过去的

代码

#include<queue>

#include<vector>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

#define LL long long

#define inf 999999999

#define lowbit(i) ((i)&(-i))

#define re register

#define maxn 5005

inline int read() {

    int x=0;char c=getchar();while(c<'0'||c>'9') c=getchar();

    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;

}

std::vector<int> v[maxn];

std::queue<int> q;

struct E{int v,nxt,f;}e[2000005];

int n,m,K,tot,ans,S,T,sz;

int num=1,a[3005],b[3005],vis[3005],pr[3005];

int st[2][5005],top[2];

int head[maxn],cur[maxn],d[maxn];

int U[900005],V[900005];

inline void add(int x,int y,int f) {e[++num].v=y;e[num].nxt=head[x];head[x]=num;e[num].f=f;}

inline void C(int x,int y,int f) {add(x,y,f),add(y,x,0);}

inline int count(int x) {

    int now=0;

    while(x) {now^=1,x-=lowbit(x);}

    return now;

}

inline int BFS() {

    cur[S]=head[S],d[T]=0,cur[T]=head[T];

    for(re int i=1;i<=sz;i++) d[pr[i]]=0,cur[pr[i]]=head[pr[i]];

    d[S]=1,q.push(S);

    while(!q.empty()) {

        int k=q.front();q.pop();

        for(re int i=head[k];i;i=e[i].nxt)

        if(e[i].f&&!d[e[i].v]) d[e[i].v]=d[k]+1,q.push(e[i].v);

    }

    return d[T];

}

int dfs(int x,int now) {

    if(x==T||!now) return now;

    int flow=0,ff;

    for(re int& i=cur[x];i;i=e[i].nxt)

    if(d[e[i].v]==d[x]+1) {

        ff=dfs(e[i].v,min(now,e[i].f));

        if(ff<=0) continue;

        now-=ff,flow+=ff,e[i].f-=ff,e[i^1].f+=ff;

        if(!now) break;

    }

    return flow;

}

inline void Dinic(int val) {

    int now=val;

    while(BFS()) {

        now-=dfs(S,inf);

        if(now<=ans) return;

    }

    ans=now;

}

inline void Connect() {

    num=1;memset(head,0,sizeof(head));

    sz=0;for(re int i=1;i<=m;i++) if(vis[i]) pr[++sz]=i;

    for(re int i=1;i<=tot;i++) if(vis[U[i]]&&vis[V[i]]) C(U[i],V[i],1);

    for(re int i=1;i<=top[0];i++) if(vis[st[0][i]]) C(S,st[0][i],1);

    for(re int i=1;i<=top[1];i++) if(vis[st[0][i]]) C(st[1][i],T,1);

}

inline void make(int x) {

    memset(vis,0,sizeof(vis));

    for(re int i=0;i<v[x].size();i++) vis[v[x][i]]++;

    int P=1;

    for(re int i=1;i<=m;i++) P+=vis[i];

    if(P<=ans) return;

    Connect();Dinic(P);

}

inline void choice(int x,int y) {

    memset(vis,0,sizeof(vis));

    for(re int i=0;i<v[x].size();i++) vis[v[x][i]]++;

    for(re int i=0;i<v[y].size();i++) vis[v[y][i]]++;

    int P=2;

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

        if(vis[i]<2) vis[i]=0;else vis[i]=1;

        P+=vis[i];

    }

    if(P<=ans) return;

    Connect();Dinic(P);

}

int main() {

    n=read(),n=read(),m=read(),K=read();S=0,T=m+1;

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

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

        b[i]=read();st[b[i]&1][++top[b[i]&1]]=i;

    }

    for(re int i=1;i<=m;i++) pr[++sz]=i;

    for(re int i=1;i<=top[0];i++)

        for(re int j=1;j<=top[1];j++)

            if(!count(b[st[0][i]]|b[st[1][j]]))

                U[++tot]=st[0][i],V[tot]=st[1][j];

    for(re int i=1;i<=tot;i++) C(U[i],V[i],1);

    for(re int i=1;i<=top[0];i++) C(S,st[0][i],1);

    for(re int i=1;i<=top[1];i++) C(st[1][i],T,1);

    Dinic(m);

    for(re int x,y,i=1;i<=K;i++) x=read(),y=read(),v[x].push_back(y);

    for(re int i=1;i<=n;i++) make(i);

    for(re int i=1;i<=n;i++)

    	for(re int j=i+1;j<=n;j++) if((a[i]^a[j])&1) choice(i,j);

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

    return 0;

}