一道比较简单的的网络流拆点题目。
首先考虑这样一种建模的想法：建超级源点S，超级汇点T，将源点与所有练习册相连，再将所有答案与汇点相连。
然后根据各练习册，书本之间的关系进行连边。然后一脸期待的跑Dinic，结果很干脆：WA
但是，为什么？
考虑这样一张图（S标为0，T标为N1+N2+N3+1，书为1到N1，练习册为N1+1到N1+N2，答案为N1+N2+1到N1+N2+N3）
对于上面的图，如果跑最大流会得到2.
但是我们发现，这样标号为1的书被使用了两次，这是不允许的！
因此我们发现每一个点的流量限制均为1，那该怎么办呢？
很简单，我们把一个点拆成两个，一个连入度的边，一个连出度的边，然后在两条边之间连一条容量为1的边，就可以完美地解决这个问题。
CODE
#include<cstdio> #include<cstring> using namespace std; const int N=10005<<2,M=1000005,INF=1e9; struct edge { int to,next,c; }e[M]; int head[N],Q[N],dep[N],n,m,p,q,x,y,s,t,k=-1; inline char tc(void) { static char fl[100000],*A=fl,*B=fl; return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++; } inline void read(int &x) { x=0; char ch=tc(); while (ch<'0'||ch>'9') ch=tc(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc(); } inline void add(int x,int y,int z) { e[++k].to=y; e[k].c=z; e[k].next=head[x]; head[x]=k; } inline int min(int a,int b) { return a<b?a:b; } inline bool BFS(void) { memset(dep,0,sizeof(dep)); Q[1]=s; dep[s]=1; int H=0,T=1; while (H<T) { int now=Q[++H]; for (register int i=head[now];i!=-1;i=e[i].next) if (!dep[e[i].to]&&e[i].c) { dep[e[i].to]=dep[now]+1; Q[++T]=e[i].to; } } return dep[t]; } inline int DFS(int now,int dist) { if (now==t) return dist; int res=0; for (register int i=head[now];i!=-1&&dist;i=e[i].next) if (dep[e[i].to]==dep[now]+1&&e[i].c) { int dis=DFS(e[i].to,min(dist,e[i].c)); dist-=dis; res+=dis; e[i].c-=dis; e[i^1].c+=dis; } if (!res) dep[now]=0; return res; } inline int Dinic(void) { int sum=0; while (BFS()) sum+=DFS(s,INF); return sum; } int main(void) { //freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout); register int i; memset(e,-1,sizeof(e)); memset(head,-1,sizeof(head)); read(n); read(p); read(q); s=0; t=2*n+p+q+1; for (i=1;i<=p;++i) add(s,i,1),add(i,s,0); for (i=1;i<=q;++i) add(i+p,t,1),add(t,i+p,0); for (i=1;i<=n;++i) add(i+p+q,i+n+p+q,1),add(i+n+p+q,i+p+q,0); read(m); for (i=1;i<=m;++i) { read(x); read(y); add(y,x+p+q,1); add(x+p+q,y,0); } read(m); for (i=1;i<=m;++i) { read(x); read(y); add(x+n+p+q,y+p,1),add(y+p,x+n+p+q,0); } printf("%d",Dinic()); return 0; }
另外，这道题和Luogu P1402 酒店之王是完全相同的建模形式（数据范围还缩小了），可以双倍经验。