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