AC了
2024-06-29 14:26:30
发布于:浙江
0阅读
0回复
0点赞
#include<cstdio>
#include<cctype>
#include<cstring>
#include<queue>
#define maxn 1000007
#define inf 0x3f3f3f3f
using namespace std;
int n1,n2,n3,m1,m2,S,T,head[maxn],num=1,d[maxn];
inline int qread() {
char c=getchar();int num=0,f=1;
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) num=num*10+c-'0';
return num*f;
}
struct node {
int v,f,nxt;
}e[1000007];
inline void ct(int u, int v, int f) {
e[++num]=node{v,f,head[u]};
head[u]=num;
}
inline bool bfs() {
memset(d,-1,sizeof(d));
queue<int>q;
q.push(S),d[S]=0;
while(!q.empty()) {
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].nxt) {
int v=e[i].v;
if(e[i].f&&d[v]==-1) {
d[v]=d[u]+1;
q.push(v);
}
}
}
return d[T]!=-1;
}
int dfs(int u, int f) {
if(u==T) return f;
int rest=0;
for(int i=head[u];i;i=e[i].nxt) {
int v=e[i].v;
if(d[v]==d[u]+1&&e[i].f) {
int t=dfs(v,min(e[i].f,f-rest));
if(!t) d[v]=0;
e[i].f-=t;
e[i^1].f+=t;
rest+=t;
if(f==rest) return rest;
}
}
return rest;
}
inline int dinic() {
int ans=0;
while(bfs()) ans+=dfs(S,inf);
return ans;
}
int main() {
n1=qread(),n2=qread(),n3=qread();
S=1,T=n1*2+n2+n3+2;
m1=qread();
for(int i=1,u,v;i<=m1;++i) {
u=qread(),v=qread();
ct(v+1,u+n2+1,1);
ct(u+n2+1,v+1,0);
}
for(int i=n2+2;i<=n2+n1+1;++i) ct(i,i+n1,1),ct(i+n1,i,0);
m2=qread();
for(int i=1,u,v;i<=m2;++i) {
u=qread(),v=qread();
ct(n2+u+n1+1,n2+2*n1+v+1,1);
ct(n2+2*n1+v+1,n2+u+n1+1,0);
}
for(int i=2;i<=n2+1;++i) ct(S,i,1),ct(i,S,0);
for(int i=n2+n1*2+2;i<=T-1;++i) ct(i,T,1),ct(T,i,0);
printf("%d\n",dinic());
return 0;
}
这里空空如也
有帮助,赞一个