求dinic改进算法
noip吧
全部回复
仅看楼主
level 3
FDR🌟烈梦 楼主
看到某讲义中有这么一段
Dinic算法具有比较高的效率,但由于要构造一个新的网络结构L,并且要不断的把L中的流拷贝到原始网络G中,在这方面浪费了比较多的时间。Dinic改进算法的思想是将G中的每一条边增加一个标志位,如果其上的容量有效,即置为TRUE;否则置为FALSE。置为FALSE的边不能参加增广,最大流是只包含TRUE边的最大流,思想同Dinic算法。改进后算法的复杂性没有改变,但执行效率提高得非常之多。
然后就神马都木有了,求哪位大牛给讲解一下,在神马情况下一条边上的容量才有效?
2011年04月28日 14点04分 1
level 6
[揉脸]
2011年04月28日 15点04分 2
level 7
你确定这个是Dinic?
2011年04月28日 15点04分 3
level 6
表示改进前的DINIC都看不懂了,改进后的更加看不懂。。。
2011年04月28日 15点04分 4
level 9
同求
2011年04月28日 15点04分 5
level 3
FDR🌟烈梦 楼主
喂喂喂…真没人懂了麽…
2011年04月28日 23点04分 6
1