求助Dinic
  • 板块学术版
  • 楼主Zxx200611
  • 当前回复2
  • 已保存回复2
  • 发布时间2020/7/21 14:03
  • 上次更新2023/11/6 22:41:15
查看原帖
求助Dinic
175590
Zxx200611楼主2020/7/21 14:03

RTRT,爆空间了,目前看来是爆队列或者爆栈的问题,求查错。
网络流代码:

bool get_dep()
{
	memset(dep,0,sizeof(dep));
	q.push(1);
	dep[1]=1;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int v=1;v<=totn;v++)
		{
			if(dep[v]||!G[u][v])
			{
				continue;
			}
			dep[v]=dep[u]+1;
			q.push(v);
		}
	}
	return dep[2]!=0;
}
int get_del(int u,int flow)
{
	if(u==2||!flow)
	{
		return flow;
	}
	int max_flow=0;
	for(int &v=cur[u];v<=totn;v++)
	{
		if(dep[u]+1!=dep[v]&&!G[u][v])
		{
			continue;
		}
		int del_flow=get_del(v,min(flow,G[u][v]));
		if(del_flow)
		{
			G[u][v]-=del_flow;
			G[v][u]+=del_flow;
			max_flow+=del_flow;
			flow-=del_flow;
			if(!flow)
			{
				break;
			}
		}
		else
		{
			dep[v]=0;
		}
	}
	return max_flow;
}
int Dinic()
{
	int max_flow=0;
	while(get_dep())
	{
		memset(cur,0,sizeof(cur));
		int flow;
		while(flow=get_del(1,1e9))
		{
			max_flow+=flow;
		}
	}
	return max_flow;
}
2020/7/21 14:03
加载中...