[洛谷P1231] 教辅的组成

题目大意：有n1本书，n2本练习册和n3个答案，然后又一些条件，说明某本答案可能和某本书对应，某本练习册可能和某本书对应，求最多有多少本完整的书（有书，练习册，答案）

题解：网络流，对应就连边，然后考虑一本书可能有多条边相连导致答案变大，就把书拆成两个点，边权为1

卡点：1.前向星cnt初值为0，就有一条边无法遍历到，应该赋2

 

C++ Code:

#include<cstdio>
#include<cstring>
using namespace std;
const int inf=0x3f3f3f3f;
inline int min(int a,int b){return a<b?a:b;}
int n1,n2,n3,m1,m2;
int a,b,end,start=1;
int cnt=2,head[50010];
int d[50010];
struct Edge{
	int to,nxt,cost;
}e[150010];
int q[150010],h,t;
void add(int a,int b,int c){
	e[cnt]=(Edge){b,head[a],c};head[a]=cnt;
	e[cnt^1]=(Edge){a,head[b],0};head[b]=cnt^1;
	cnt+=2;
}
bool bfs(){
	memset(d,0,sizeof d);
	d[q[h=t=1]=start]=1;
	while (h<=t){
		int x=q[h++];
//		if (x==end)printf("%d\n",d[end]);
		if (x==end)return true;
		for (int i=head[x];i;i=e[i].nxt){
			int to=e[i].to;
			if ((!d[to])&&e[i].cost){
				d[to]=d[x]+1;
				q[++t]=to;
			}
		}
	}
	return d[end];
}
int dfs(int x,int low){
	if ((x==end))return low;
	int res=0,w;
	for (int i=head[x];i;i=e[i].nxt){
		int to=e[i].to;
		if ((d[to]==d[x]+1)&&e[i].cost){
			w=dfs(to,min(low-res,e[i].cost));
//			printf("%d\n",w);
			e[i].cost-=w;
			e[i^1].cost+=w;
			res+=w;
			if (res==low)return res;
		}
	}
	if (!res)d[x]=-1;
	return res;
}
void dinic(){
	int ans=0;
	while (bfs()){
		int k=dfs(start,inf);
		if (k>0)ans+=k;
//		printf("%d\n",ans);
	}
	printf("%d\n",ans);
}
int main(){
	scanf("%d%d%d",&n1,&n2,&n3);
	scanf("%d",&m1);
	for (int i=0;i<m1;i++){
		scanf("%d%d",&a,&b);
		add(b+1,n2+a+1,1);
	}
	scanf("%d",&m2);
	for (int i=0;i<m2;i++){
		scanf("%d%d",&a,&b);
		add(n1+n2+a+1,(n1<<1)+n2+b+1,1);
	}
	end=(n1<<1)+n2+n3+2;
	for (int i=1;i<=n2;i++)add(start,i+1,1);
	for (int i=1;i<=n3;i++)add((n1<<1)+n2+i+1,end,1);
	for (int i=1;i<=n1;i++)add(n2+i+1,n1+n2+i+1,1);
	dinic();
	return 0;
}