传送门

Solution

考虑一本书最多用一次，所以拆点。

其他的答案、练习册与书本的限制直接连1的边就好了。

最后跑出来的最大流就是答案。

代码实现

#include
    
     using namespace std;const int N=100010,Inf=1e9+10;int front[N],cnt,s,t,n1,n2,n3;struct node{    int to,nxt,w;}e[500010];queue
     
      Q;int dep[N];void Add(int u,int v,int w){    e[cnt]=(node){v,front[u],w};front[u]=cnt++;    e[cnt]=(node){u,front[v],0};front[v]=cnt++;}bool bfs(){    memset(dep,0,sizeof(dep));    Q.push(s);dep[s]=1;    while(!Q.empty())    {        int u=Q.front();Q.pop();        for(int i=front[u];i!=-1;i=e[i].nxt)        {            int v=e[i].to;            if(!dep[v] && e[i].w)            {                dep[v]=dep[u]+1;Q.push(v);            }        }                           }    return dep[t];}int dfs(int u,int flow){    if(u==t || !flow)return flow;    for(int i=front[u];i!=-1;i=e[i].nxt)    {        int v=e[i].to;        if(dep[v]==dep[u]+1 && e[i].w)        {            int di=dfs(v,min(flow,e[i].w));            if(di)            {                e[i].w-=di;e[i^1].w+=di;                return di;            }            else dep[v]=0;        }    }    return 0;}int dinic(){    int flow=0;    while(bfs())    {        while(int d=dfs(s,Inf))flow+=d;    }    return flow;}int m;int main(){    memset(front,-1,sizeof(front));    scanf("%d%d%d",&n1,&n2,&n3);t=n1*2+n2+n3+1;    scanf("%d",&m);    for(int i=1;i<=n2;i++)        Add(s,i,1);    for(int i=1;i<=n1;i++)        Add(i+n2,i+n1+n2+n3,1);    while(m--)    {        int x,y;scanf("%d%d",&x,&y);        Add(y,x+n2,1);    }    scanf("%d",&m);    for(int i=1;i<=n3;i++)        Add(i+n1+n2,t,1);    while(m--)    {        int x,y;scanf("%d%d",&x,&y);        Add(n1+n2+n3+x,y+n1+n2,1);    }    printf("%d\n",dinic());    return 0;}