Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:第一个网络流 ,纪念下~ 我的一点总结

Posted by alwaysinfaith at 2011-10-29 20:57:41 on Problem 1273
In Reply To:第一个网络流 ,纪念下~ 我的一点总结 Posted by:1272406003 at 2009-07-28 15:34:22
> 网络流一直没敢学,终于还是学了。
> 主要参考了两本书:《算法导论》《算法艺术与信息学竞赛》
> 
> 《算法导论》介绍了四种求最大流的方法,前两种Ford-Fulkerson和Edmonds-Karp算法
> 
> 这两种算法相对来说很好理解,但时间效率不高。对于边数很多的情况下不是一种很好的算法。
> 
> 许多关于最大流问题的渐近最快速算法就是压入和重标记算法,它的时间复杂度可以达到
> O(v^2*E),是对Edmons-karp算法时间复杂度O(V*E^2)的一种改进。
> 
> 对一般性压入与重标记算法进一步精化,可以得到另一种运行时间O(V^3)的压入与从标记算法。
> 
> 看来PUSH-RELABER 算法还是王道!膜拜!!!!!

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


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