提问,为什么每次增广路只能找一条
查看原帖
提问,为什么每次增广路只能找一条
251882
蒟蒻丁楼主2020/8/7 21:19
ll dfs(ll x,ll flow){
	if(x==t)return flow;
	ll ret=flow,k;
	for(ll i=head[x];(~i)&&ret;i=q[i].nxt){
		ll v=q[i].to;
		if(dep[v]==dep[x]+1&&q[i].ff){
			k=dfs(v,min(flow,q[i].ff));
			ret-=k;
			q[i].ff-=k;
			q[i^1].ff+=k;
		}
	}
	return flow-ret;
}

这个WA了,

ll dfs(ll x,ll flow){
	if(x==t)return flow;
	ll ret=flow,k;
	for(ll i=head[x];(~i)&&ret;i=q[i].nxt){
		ll v=q[i].to;
		if(dep[v]==dep[x]+1&&q[i].ff){
			k=dfs(v,min(flow,q[i].ff));
			if(k>0){
				ret-=k;
				q[i].ff-=k;
				q[i^1].ff+=k;
				return k;
			}
				
		}
	}
	return 0;
}

后来发现题解都这么写,就改了一下,A了

但是我一直写的都是第一个,都能过啊,为什么这次不行

2020/8/7 21:19
加载中...