网络流dinic模板

时间:2022-11-26 04:29:10
bool makelevel()
{
	memset(level,-1,sizeof(level));
	q[1]=0;
	level[0]=0;
	head=1,tail=1;
	for(int head=1;head<=tail;head++)
	{
		for(int i=lin[q[head]];i;i=e[i].next)
		{
			if(level[e[i].y]<0&&e[i].v>0)
			{
				level[e[i].y]=level[q[head]]+1;
				q[++tail]=e[i].y;
			}
		}
	}
	return level[n+m+1]>=0;
}
int MAXflow(int aa,int flow)
{
	if(aa==n+m+1)return flow;
	int maxflow=0,d=0;
	for(int i=lin[aa];i&&maxflow<flow;i=e[i].next)
	{
		if(e[i].v&&level[e[i].y]==level[aa]+1)
		{
			if(d=MAXflow(e[i].y,min(flow-maxflow,e[i].v)))
			{
				e[i].v-=d;
				e[e[i].h].v+=d;
				maxflow+=d;
			}
		}
	}
	if(maxflow<=0) level[aa]=-1;
	return maxflow;
}
void dinic()
{
	int d;
	while(makelevel())
		while(d=MAXflow(0,99999999))
				ans+=d;
}