rt,在最大流模板题中,我使用了如下代码:
LL Dinic(){
LL res=0,tmp;
while(bfs()){
res+=find(s,INF);
assert(!find(s,INF));
}
return res;
}
没有报告异常,并且在多题中都没有发现异常,现在给出一个结论,求问是否正确:
只需要 INF 足够大,就不需要多次增广,即可以将如下代码替换成上方的:
LL Dinic(){
LL res=0,tmp;
while(bfs())
while(tmp=find(s,INF))
res+=tmp;
return res;
}
一个简略的说明:当 INF 足够大时,能够将 S 流出的流量视作多次增广的总流量,两者等价,故上述结论成立。
求问:上述说明是否正确?上述结论是否正确?
以及,如果有一道题不能用上述方法替换,请回复。
注意: 这个帖子没有特别的实际意义,因为效率根本没有什么提升。
另外: 对于 INF 在总边数乘最大容量爆了可存最大值时,完全不需要担心,因为此时答案也会爆,所以可以保证 INF 足够大时能够使用上述替换方法。