首页 > 代码库 > 北大ACM暑期培训课程目录(五)
北大ACM暑期培训课程目录(五)
本文出自:http://blog.csdn.net/svitter
netFlow
Ford-Fulkerson
深度优先搜索,制作一个流网络。
部分路径可能不合理。
对上次dfs的边就行重新筛选。每条边来个反向边。
再来一次dfs
发现还能找到一条路径。
dfs->abtray edge->dfs
stop when no new stream
容量相等。
*残余网络
寻找变数最少的增广路径
通过bfs寻找增广路劲
Edmonds-Karp最短增广路算法
依然不是很好的算法。
POJ1273模板题
Dinic快速网络流算法
有方向的DFS(deep find search?)
1.首先利用bfs分层
2.必须走下一层节点。
3.回溯。
4.回溯原点,dfs结束。
5.重新分层。(若无法走到汇点,算法结束)否则,返回1.
复杂度n*n*m
以上是最大流
最大流每条边上的流量,最大是多少。
把原图备份,再减去最大流的流量。
最大流和上下界的部分待日后补充。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。