首页 > 其他 > 详细

ACM 第六天

时间:2018-07-28 11:24:44      阅读:129      评论:0      收藏:0      [点我收藏+]

图论 网络流

最大流 INF(初始值)

路径上权值最小的边,决定流量大小。

 

流量网络的三个特性:

①流量控制

②反对称性

③流量守恒

 

残余网络:保留了c(e)容量<f(e)流量【可以继续流,因为还有f(e)-c(e)的流量】和 c(e)>0的反向边【可以回退】

 增广路定理:网络中达到最大流当且仅当残余网络中不存在增广路。

所以总结做题方法就是不断找增广路,有三种方法:

①Ford-Fvkerson(DFS)

伪代码:

不断地在残余网络中找增广路伪代码:

FF{

flow=0;

while(true)

{

 

}

DFS遍历传参伪代码过程:

dfs(int now,int t,int cnt)

{

if(now==t) return cnt;

for(i)

if(!vis[i] && cap>0)

vis[i]=true;

d=dfs(next,t,min(cnt,cap)

if(d>0)

else

return 0;

}

 

两个技巧:①邻接表

②邻接矩阵 [i][j]=cap [j][i]=0;

 

ACM 第六天

原文:https://www.cnblogs.com/weixq351/p/9380663.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!