跑得还没ek快,是不是哪里写假了
#include <iostream>
#include <queue>
#include <cstring>
#define maxn 50005
#define inf 0x7f7f7f7f
using namespace std;
int n,n1,n2,n3,m1,m2,u,v,s,t,ans;
int cnt=1,head[maxn],dis[maxn],gap[maxn];
struct edge{
int v,w,nxt;
}e[1000000];
void add(int u,int v,int w){
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].nxt=head[u];
head[u]=cnt;
}
void bfs(){
queue<int> q;q.push(t);
memset(dis,-1,sizeof dis);
dis[t]=0;gap[0]=1;
while (q.size()){
int tmp=q.front();q.pop();
for (int i=head[tmp];i;i=e[i].nxt){
if (e[i^1].w&&dis[e[i].v]==-1){
dis[e[i].v]=dis[tmp]+1;
gap[dis[e[i].v]]++;
q.push(e[i].v);
}
}
}
}
int dfs(int now,int flow){
if (now==t) return flow;
int used=0;
for (int i=head[now];i;i=e[i].nxt){
if (e[i].w&&dis[e[i].v]+1==dis[now]){
int f=dfs(e[i].v,min(flow-used,e[i].w));
used+=f;
e[i].w-=f;
e[i^1].w+=f;
if (used==flow) return flow;
}
}
if (!(--gap[dis[now]])) dis[now]=n1*2+n2+n3+1;
dis[now]++;
gap[dis[now]]++;
return used;
}
int main(){
// freopen("P1231_2.in","r",stdin);
ios::sync_with_stdio(false);
cin>>n1>>n2>>n3>>m1;
s=0;t=n1*2+n2+n3+1;
for (int i=1;i<=m1;i++){
cin>>u>>v; u+=n2;
add(v,u,1);add(u,v,0);
}
for (int i=n2+1;i<=n1+n2;i++){
add(i,i+n1,1);add(i+n1,i,0);
}
cin>>m2;
for (int i=1;i<=m2;i++){
cin>>u>>v;u+=(n2+n1);v+=(n1*2+n2);
add(u,v,1);add(v,u,0);
}
for (int i=1;i<=n2;i++){
add(s,i,1);add(i,s,0);
}
for (int i=n2+n1*2+1;i<=t-1;i++){
add(i,t,1);add(t,i,0);
}
bfs();
while (dis[s]<n1*2+n2+n3+1){
ans+=dfs(s,inf);
}
cout<<ans;
}