关于Dinic单次增广次数
  • 板块学术版
  • 楼主Comentropy泠云
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/1/9 22:44
  • 上次更新2024/1/10 21:33:18
查看原帖
关于Dinic单次增广次数
264360
Comentropy泠云楼主2024/1/9 22:44

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 足够大时能够使用上述替换方法。

2024/1/9 22:44
加载中...