Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

做了一个 O(e*log(f)) 的 EK 最大瓶颈增广路算法, 结果效果不好对于这个题目, log(f)应该不大于32, 效率应该很高才对啊

Posted by semonteer at 2006-06-27 22:38:34 on Problem 1459
In Reply To:开始用邻接表做本题就超时，改成邻接矩阵做就AC了~~ Posted by:xiedi at 2004-05-11 16:46:17

> 真折腾人~~~~~
> 以后最大流还是少用邻接表……

Followed by:

大O记号的意义你理解么？ (0) frkstyc 2006-06-27 22:39:42
- 不了解 (0) oeym 2006-06-27 22:41:16
- 常数的问题, 了解一些 (0) semonteer 2006-06-27 22:42:55
- 那么也就是说如果规模更大些, 才能体现出优势? 这个算法也称作伪多项式算法么 (0) semonteer 2006-06-27 22:56:41
  - 这个很难说的，要让时间达到bound往往需要一些特殊的网络 (0) frkstyc 2006-06-27 23:11:24
- 您好, 我想了一下, 书上说最多进行log(f)次迭代,f是最终的最大流数值, 每次迭代O(e), 然后对比一下,和我以前的程序相比,常数应该说比较小,我也是用类似prim的贪心法找最大瓶颈路,指点一下吧 (1395) semonteer 2006-06-27 23:16:34
  - 我记得capacity scaling是O(E^2lgC)的吧 (1491) frkstyc 2006-06-27 23:27:58
    - 要进行 e*log(c) 次迭代? (0) semonteer 2006-06-27 23:31:26
    - sorry 我错了 (0) semonteer 2006-06-28 00:01:50
      - 为什么这么菜... (0) semonteer 2006-06-28 00:02:06

Post your reply here:

Home Page Go Back To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator