wforscheckd 2011-12-02 04:17:00
点我顶贴
收藏
删除
网络流算法都很慢的，最快的hlpp n*n*sqrt(m),可是这题却用sap,dinic都可以过，本题点和边数这么多,按照时间复杂度根本就过不了啊时间上来算少说要几百年才能算出来,什么原因？？
#1 dingjian0312@2011-12-02 04:17:00
24150
回复
删除
回复 楼主wforscheckd 的帖子
复杂度只是计算一个算法的最坏情况。。这题的图比较特殊，几乎是二分图，而dinic和sap用的是最短增广路，所以运行起来自然快。
#2 Palca@2014-05-13 23:23:36
32647
回复
删除
复杂度计算了算法运行的下界，这个下界对实际的情形（甚至理论的）不一定足够紧，而且还有常数的问题，比如：0.05n^2和10000n^2都是O(n^2)的。