[LuoguP1231]教辅的组成

# 分析 一道网络流模板 首先要把书，练习册，答案的结点分开 分开后，如果直接利用题中信息建网络跑最大流的话，会同一书使用多次的情况，因此需要拆点处理 ![p1][1] 0和21分别为源点和汇点，1-5为书，6-10为它们对应的副本，11-15为练习册，16-20为答案 # 代码 ```cpp #include<cstdio> #include<queue> #include<cstring> #include<algorithm> using namespace std; const int N=5e4+4,M=2e5+5,INF=0x3f3f3f3f; int n1,n2,n3,m1,m2,s,t,maxflow; struct qxx{int nex,t,v;}; qxx e[M]; int h[N],cnt=1; void add_path(int f,int t,int v){e[++cnt]=(qxx){h[f],t,v},h[f]=cnt;} void add_flow(int f,int t,int v){add_path(f,t,v);add_path(t,f,0);} int d[N],cnr[N]; bool bfs(){ memset(d,0,sizeof(d)); memcpy(cnr,h,sizeof(h)); queue<int> q; q.push(s),d[s]=1; while(q.size()){ int u=q.front();q.pop(); for(int i=h[u];i;i=e[i].nex){const int &v=e[i].t,&w=e[i].v; if(!d[v]&&w)d[v]=d[u]+1,q.push(v); } } return d[t]; } int dinic(int u,int flow){ if(u==t)return flow; int x,rest=flow; for(int i=cnr[u];i&&rest;i=e[i].nex){const int &v=e[i].t,&w=e[i].v; cnr[u]=i; if(!w||d[v]!=d[u]+1)continue; x=dinic(v,min(rest,w)); if(x)e[i].v-=x,e[i^1].v+=x,rest-=x; else d[v]=0; } if(rest)d[u]=0; return flow-rest; } int main(){ //书：1-n1； //书2:n1+1~n1+n1; //练习册:n1+n1+1~n1+n1+n2 //答案n1+n1+n2+1~n1+n1+n2+n3 scanf("%d%d%d%d",&n1,&n2,&n3,&m1); for(int i=1;i<=m1;i++){int x,y; scanf("%d%d",&x,&y); add_flow(x,n1+n1+y,1); } scanf("%d",&m2); for(int i=1;i<=m2;i++){int x,y; scanf("%d%d",&x,&y); add_flow(n1+n1+n2+y,n1+x,1); } s=0,t=n1+n1+n2+n3+1; for(int i=1;i<=n3;i++)add_flow(s,i+n1+n1+n2,1); for(int i=1;i<=n1;i++)add_flow(i+n1,i,1); for(int i=1;i<=n2;i++)add_flow(i+n1+n1,t,1); while(bfs())for(int fl=dinic(s,INF);fl;fl=dinic(s,INF))maxflow+=fl; printf("%d",maxflow); return 0; } ``` [1]: https://hexo-source-1257756441.cos.ap-chengdu.myqcloud.com/2018/12/21/10.png