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

求教：Ford-Fulkerson 求最小费用最大流的复杂度是多少？点n个边m条，用邻接表表示图。。

Posted by BLUEWIND at 2007-10-21 21:38:59

Followed by:

朴素实现是O(EF)，E是边数F是最大流量 (0) wywcgs 2007-10-22 10:50:31
- 改进了的是什么，有没有跟流量F无关，而跟点数N，边数M有关的算法？ (0) bluewind 2007-10-22 12:31:56
  - bfs找最短增广路径增广，可以达到O(VE^2) (0) wywcgs 2007-10-22 12:56:53
    - 这好像不是费用流的复杂度吧，教主？？ (2) frogxx 2007-10-22 13:37:06
      - 哦，抱歉，最近大脑故障了 (30) wywcgs 2007-10-22 13:44:27

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