求助帖
查看原帖
求助帖
224358
清平乐楼主2020/8/11 18:32

为什么 Dinic\text{Dinic} 这样写 DFS\text{DFS} 这个题会 T

int DFS(int u,int flow)
{
	if(u==t) return flow;
	register int res=0;
	for(register int &i=now[u];flow&&i;i=e[i].next)
		if(e[i].w&&d[e[i].v]==d[u]+1)
		{
			register int t=DFS(e[i].v,min(flow,e[i].w));
			if(!t) d[e[i].v]=INF;
			e[i].w-=t,e[i^1].w+=t;
			flow-=t,res+=t;
		}
	return res;
}

这样就过了,还跑得飞快

int DFS(int u,int flow)
{
	if(u==t) return flow;
	register int res=0;
	for(register int &i=now[u];i;i=e[i].next)
		if(e[i].w&&d[e[i].v]==d[u]+1)
		{
			register int t=DFS(e[i].v,min(flow,e[i].w));
			if(!t) d[e[i].v]=INF;
			e[i].w-=t,e[i^1].w+=t;
			flow-=t,res+=t;
			if(!flow) break;
		}
	return res;
}

之前的题都没有出锅
我寻思这两种写法不是等价的吗

2020/8/11 18:32
加载中...