漂亮小姐姐点击就送：https://www.luogu.org/problemnew/show/P1231
题目背景
滚粗了的HansBug在收拾旧语文书，然而他发现了什么奇妙的东西。
题目描述
蒟蒻HansBug在一本语文书里面发现了一本答案，然而他却明明记得这书应该还包含一份练习题。然而出现在他眼前的书多得数不胜数，其中有书，有答案，有练习册。已知一个完整的书册均应该包含且仅包含一本书、一本练习册和一份答案，然而现在全都乱做了一团。许多书上面的字迹都已经模糊了，然而HansBug还是可以大致判断这是一本书还是练习册或答案，并且能够大致知道一本书和答案以及一本书和练习册的对应关系（即仅仅知道某书和某答案、某书和某练习册有可能相对应，除此以外的均不可能对应）。既然如此，HansBug想知道在这样的情况下，最多可能同时组合成多少个完整的书册。
输入输出格式
输入格式：
第一行包含三个正整数N1、N2、N3，分别表示书的个数、练习册的个数和答案的个数。
第二行包含一个正整数M1，表示书和练习册可能的对应关系个数。
接下来M1行每行包含两个正整数x、y，表示第x本书和第y本练习册可能对应。（1<=x<=N1，1<=y<=N2）
第M1+3行包含一个正整数M2，表述书和答案可能的对应关系个数。
接下来M2行每行包含两个正整数x、y，表示第x本书和第y本答案可能对应。（1<=x<=N1，1<=y<=N3）
输出格式：
输出包含一个正整数，表示最多可能组成完整书册的数目。
输入输出样例
说明
样例说明：
如题，N1=5，N2=3，N3=4，表示书有5本、练习册有3本、答案有4本。
M1=5，表示书和练习册共有5个可能的对应关系，分别为：书4和练习册3、书2和练习册2、书5和练习册2、书5和练习册1以及书5和练习册3。
M2=5，表示数和答案共有5个可能的对应关系，分别为：书1和答案3、书3和答案1、书2和答案2、书3和答案3以及书4和答案3。
所以，以上情况的话最多可以同时配成两个书册，分别为：书2+练习册2+答案2、书4+练习册3+答案3。
数据规模：
对于数据点1, 2, 3，M1，M2<= 20
对于数据点4~10，M1，M2 <= 20000
// luogu-judger-enable-o2 // luogu-judger-enable-o2 //源点向书连边，书向练习册连边，将答案和练习册拆点，容量为1，防止选多次 //练习册向答案连边，答案向汇点连边 //图中流量全为1 //跑最大流即为ans //有个更好的建图方法 //我们让源点和练习册连边，练习册和书连边，书和答案连边，答案和汇点连边 //这样，因为现在是练习册去找书，我们就把书拆点 //练习册和答案不拆点 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=5e4+5; const int M=5e5+5; const int INF=0x7fffffff; int n1,n2,n3,m,S,T; int head[N],num_edge; struct Edge { int v,flow,nxt; }edge[M<<1]; inline int read() { char c=getchar();int num=0,f=1; for(;!isdigit(c);c=getchar()) f=c=='-'?-1:f; for(;isdigit(c);c=getchar()) num=num*10+c-'0'; return num*f; } inline void add_edge(int u,int v,int flow) { edge[++num_edge].v=v; edge[num_edge].flow=flow; edge[num_edge].nxt=head[u]; head[u]=num_edge; } int dep[N]; inline bool bfs() { memset(dep,0,sizeof(dep)); queue<int> que; que.push(S),dep[S]=1; int now,v; while(!que.empty()) { now=que.front(),que.pop(); for(int i=head[now];i;i=edge[i].nxt) { if(edge[i].flow) { v=edge[i].v; if(dep[v]) continue; dep[v]=dep[now]+1; if(v==T) return 1; que.push(v); } } } return 0; } int dfs(int now,int flow) { if(now==T) return flow; int outflow=0,tmp,v; for(int i=head[now];i;i=edge[i].nxt) { if(edge[i].flow) { v=edge[i].v; if(dep[v]!=dep[now]+1) continue; tmp=dfs(v,min(flow,edge[i].flow)); if(tmp) { edge[i].flow-=tmp; edge[i^1].flow+=tmp; outflow+=tmp; flow-=tmp; if(!flow) return outflow; } } } dep[now]=0; return outflow; } int main() { // freopen("testdata.in","r",stdin); num_edge=1; n1=read(),n2=read(),n3=read(); T=n2+n3+n1*2+1; for(int i=1;i<=n2;++i) { add_edge(S,i,1); //源点和练习册连边 add_edge(i,S,0); } for(int i=1;i<=n1;++i) { add_edge(i+n2,i+n1+n2,1); //把书拆点 add_edge(i+n1+n2,i+n2,0); } for(int i=1;i<=n3;++i) { add_edge(i+n1*2+n2,T,1); add_edge(T,i+n1*2+n2,0); } m=read(); for(int i=1,a,b,c;i<=m;++i) { a=read(),b=read(); a=a+n2; add_edge(b,a,1); //练习册和书连边 add_edge(a,b,0); } m=read(); for(int i=1,a,b,c;i<=m;++i) { a=read(),b=read(); a+=n2+n1; //书的第二个点 b+=n2+n1*2; add_edge(a,b,1); add_edge(b,a,0); } int Flow=0; while(bfs()) Flow+=dfs(S,INF); printf("%d",Flow); return 0; }