讨论 / 问问!对网络流的疑问,(NOI最大获利)
wforscheckd 2011-12-02 04:17:00
点我顶贴 收藏 删除
网络流算法都很慢的,最快的hlpp n*n*sqrt(m),可是这题却用sap,dinic都可以过,本题点和边数这么多,按照时间复杂度根本就过不了啊时间上来算少说要几百年才能算出来,什么原因??
#1 dingjian0312@2011-12-02 04:17:00
回复 删除
回复 楼主wforscheckd 的帖子

复杂度只是计算一个算法的最坏情况。。这题的图比较特殊,几乎是二分图,而dinic和sap用的是最短增广路,所以运行起来自然快。

#2 Palca@2014-05-13 23:23:36
回复 删除
复杂度计算了算法运行的下界,这个下界对实际的情形(甚至理论的)不一定足够紧,而且还有常数的问题,比如:0.05n^2和10000n^2都是O(n^2)的。
查看更多回复
提交回复