@[JACKLOVETHREE](/space/show?uid=34941)
by 早右昕 @ 2017-10-28 10:23:39
这个。。。。
by xyx_xcc @ 2017-10-28 10:26:52
明白了，书需要拆点，不然一本书可能会匹配多个答案，是我自己没弄清楚。新人惨痛教训OTz。
新代码如下：
```cpp
#include<bits/stdc++.h>
#define MAXN 1000000
using namespace std;
struct node {
int v,w,nxt;
} e[MAXN];
int head[MAXN],cnt(1);
void adde(int u,int v,int w) {
e[++cnt]=(node){ v,w,head[u]},head[u]=cnt;
e[++cnt]=(node){ u,0,head[v]},head[v]=cnt;
}
int n1,n2,n3,m1,m2,st,en;
int Que[MAXN],lev[MAXN],hd,tl;
bool bfs() {
memset(lev,0,sizeof lev);
Que[1]=st,lev[st]=1;
hd=0,tl=1;
int u,v,i;
while(hd<tl) {
u=Que[++hd];
for(i=head[u];i;i=e[i].nxt) {
v=e[i].v;
if(!lev[v] && e[i].w>0) {
lev[v]=lev[u]+1;
Que[++tl]=v;
}
}
}
if(lev[en]!=0) return 1;
else return 0;
}
int dfs(int u,int tot) {
if(u==en) return tot;
int i,v,all=0,temp;
for(i=head[u];i;i=e[i].nxt) {
v=e[i].v;
if(lev[v]==lev[u]+1 &&e[i].w>0 && all<tot) {
temp=dfs(v,min(tot-all,e[i].w)) ;
all+=temp;
e[i].w-=temp;
e[i^1].w+=temp;
}
}
if(all==0) lev[u]=0;
return all;
}
int dinic() {
int tot=0;
while(bfs()) tot+=dfs(st,666666666);
return tot;
}
int main() {
scanf("%d%d%d",&n1,&n2,&n3);
int u,v,i;
/*
源点：0，汇点：n1+n1+n2+n3+1
练习册：n2，1~n2
书1：n1，n2+1~n1+n2
书2：n1, n1+n2+1,n1+n1+n2
答案：n3,n1+n1+n2+1,n1+n1+n2+n3
源点->练习册->书1->书2->答案->汇点
*/
st=0,en=n1+n1+n2+n3+1;
scanf("%d",&m1);
while(m1--) {
scanf("%d%d",&u,&v);//书1，练习册
adde(v,u+n2,1);
}
scanf("%d",&m2);
while(m2--) {
scanf("%d%d",&u,&v);//书2，答案
adde(n1+n2+u,n1+n1+n2+v,1);
}
for(int i=1;i<=n1;i++) {
adde(n2+i,n1+n2+i,1);//书1，书2
}
for(int i=1;i<=n2;i++) {
adde(st,i,1);//源点，练习册
}
for(int i=1;i<=n3;i++) {
adde(n1+n1+n2+i,en,1);//答案，汇点
}
printf("%d\n",dinic());
}
```
by 早右昕 @ 2017-10-28 10:55:01
已结贴
by 早右昕 @ 2017-10-28 11:01:59