[洛谷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;

}