关于网络流的普通残留网络增广和分层图增广的问题
不太清楚普通残留网络(ford_fulkerson算法)和使用分层图网络(dinic)流进行增广有什么区别,分层图的优势在哪里?
自己回答自己把,dinic也是一种增广路算法,优势之处在于用广搜建立分层图之后可以对该图多次增广,通过一些搜索的策略设计可以使均摊时间复杂度达到O(n),而一直采用广度优先搜索来增广则每次增广时间复杂度都要达到O(m),n为点的数量,m为边的数量。
所以优势就在于它的增广路寻找的更快