| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1156 人关注过本帖
标题:关于网络流的普通残留网络增广和分层图增广的问题
只看楼主 加入收藏
朱涛
Rank: 2
等 级:论坛游民
帖 子:6
专家分:15
注 册:2010-7-30
收藏
 问题点数:0 回复次数:1 
关于网络流的普通残留网络增广和分层图增广的问题
不太清楚普通残留网络(ford_fulkerson算法)和使用分层图网络(dinic)流进行增广有什么区别,分层图的优势在哪里?
搜索更多相关主题的帖子: 网络 增广 分层 
2010-08-02 12:27
朱涛
Rank: 2
等 级:论坛游民
帖 子:6
专家分:15
注 册:2010-7-30
收藏
得分:0 
自己回答自己把,dinic也是一种增广路算法,优势之处在于用广搜建立分层图之后可以对该图多次增广,通过一些搜索的策略设计可以使均摊时间复杂度达到O(n),而一直采用广度优先搜索来增广则每次增广时间复杂度都要达到O(m),n为点的数量,m为边的数量。
所以优势就在于它的增广路寻找的更快

当做必做,坚持完成
2010-08-03 16:08
快速回复:关于网络流的普通残留网络增广和分层图增广的问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.044409 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved