最大流算法小结

忘是亡心i 2021-11-01 13:28 304阅读 0赞

<table style="border-collapse:collapse;"> 
 <tbody> 
 <tr> 
 <td align="center">最大流算法小结 </td> 
 </tr> 
 <tr> 
 <td></td> 
 </tr> 
 <tr> 
 <td></td> 
 </tr> 
 <tr> 
 <td align="center"> 
 <table style="border-collapse:collapse;"> 
 <tbody> 
 <tr> 
 <td> 
 <div> 
 &nbsp;&nbsp; 最近在看网络流，把几个常用的算法总结下，正确性的证明和一些理论的东西就不写了，参看算法导论和神牛们的论文，我只写算法的理解和实现模板。 Ford-Fulkerson方法 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;每次找增广路，把这条路上的所有点的流量加上这条路上的残余容量，再找新的增广路，直到找不到为止，它有很多种实现方法，下面给出算法导论上的伪代码 
 <div style="font-size:13px;border:#cccccc 1px solid;"> 
 <img src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif" align="top" alt="ExpandedBlockStart.gif"> 
 <img src="http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif" align="top" alt="ContractedBlock.gif"> 
 Ford_Fulkerson(&nbsp;G,&nbsp;s,&nbsp;t&nbsp;) 
 
 { <img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align="top" alt="InBlock.gif">&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;each&nbsp;edge(&nbsp;u,&nbsp;v&nbsp;)∈E[G] <img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align="top" alt="InBlock.gif">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;do&nbsp;&nbsp;&nbsp;&nbsp;f[u,v]=&nbsp;0 <img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align="top" alt="InBlock.gif">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;f[v,u]=&nbsp;0 <img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align="top" alt="InBlock.gif">&nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;there&nbsp;exists&nbsp;a&nbsp;path&nbsp;p&nbsp;from&nbsp;s&nbsp;to&nbsp;t&nbsp;in&nbsp;the&nbsp;residual&nbsp;network&nbsp;Gf <img src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif" align="top" alt="ExpandedSubBlockStart.gif"><img src="http://www.cppblog.com/Images/OutliningIndicators/ContractedSubBlock.gif" align="top" alt="ContractedSubBlock.gif">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;do&nbsp;&nbsp;&nbsp;&nbsp;Cf(p)=&nbsp;min{&nbsp;Cf(u,v)&nbsp;|&nbsp;(u,v)&nbsp;is&nbsp;in&nbsp;p&nbsp;} <img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align="top" alt="InBlock.gif">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;each&nbsp;edge(u,v)&nbsp;in&nbsp;p <img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align="top" alt="InBlock.gif">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;do&nbsp;&nbsp;&nbsp;&nbsp;f[u,v]+=&nbsp;Cf(p) <img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align="top" alt="InBlock.gif">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;f[v,u]=&nbsp;-f[u,v] 
 </div> 
 Edmonds-Karp算法 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;就是用广度优先搜索来实现Ford-Fulkerson方法中对增广路径的计算，时间复杂度为O(VE 
 2) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(代码参考NOCOW) 
 
 <div style="font-size:13px;border:#cccccc 1px solid;"> 
 <img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align="top" alt="None.gif"> 
 #define 
 &nbsp;VMAX&nbsp;201 
 <img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align="top" alt="None.gif"> 
 int 
 &nbsp;n,&nbsp;m;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 // 
 分别表示图的边数和顶点数 
 <img src="http://www.cppblog.com/Images/OutliningIndicators/None.gif" align="top" alt="None.gif"> 
 int 
 &nbsp;c[VMAX][VMAX]; <img src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif" align="top" alt="ExpandedBlockStart.gif"><img src="http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif" align="top" alt="ContractedBlock.gif"> 
 int 
 &nbsp;Edmonds_Karp(&nbsp; 
 int 
 &nbsp;s,&nbsp; 
 int 
 &nbsp;t&nbsp;) 
 
 {&nbsp;&nbsp;&nbsp;&nbsp;//输入源点和汇点 <img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align="top" alt="InBlock.gif">&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;p,&nbsp;q,&nbsp;queue[VMAX],&nbsp;u,&nbsp;v,&nbsp;pre[VMAX],&nbsp;flow=&nbsp;0,&nbsp;aug; <img src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif" align="top" alt="ExpandedSubBlockStart.gif"><img src="http://www.cppblog.com/Images/OutliningIndicators/ContractedSubBlock.gif" align="top" alt="ContractedSubBlock.gif">&nbsp;&nbsp;&nbsp;&nbsp;while(true){ <img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align="top" alt="InBlock.gif">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;memset(pre,-1,sizeof(pre));&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//记录父节点 <img src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif" align="top" alt="ExpandedSubBlockStart.gif"><img src="http://www.cppblog.com/Images/OutliningIndicators/ContractedSubBlock.gif" align="top" alt="ContractedSubBlock.gif">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(&nbsp;queue[p=q=0]=s;&nbsp;p&lt;=q;&nbsp;p++&nbsp;){&nbsp;&nbsp;&nbsp;&nbsp;//广度优先搜索 <img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align="top" alt="InBlock.gif">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;u=&nbsp;queue[p]; <img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align="top" alt="InBlock.gif">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(&nbsp;v=0;&nbsp;v&lt;m&amp;&amp;pre[t]&lt;0;&nbsp;v++&nbsp;) <img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align="top" alt="InBlock.gif">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(&nbsp;c[u][v]&gt;0&nbsp;&amp;&amp;&nbsp;pre[v]&lt;0&nbsp;) <img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align="top" alt="InBlock.gif">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;pre[v]=u,&nbsp;queue[++q]=v; <img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align="top" alt="InBlock.gif">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(&nbsp;pre[t]&gt;=0&nbsp;)&nbsp;&nbsp;&nbsp;&nbsp;break; <img src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif" align="top" alt="ExpandedSubBlockEnd.gif">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} <img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align="top" alt="InBlock.gif">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(&nbsp;pre[t]&lt;0&nbsp;)&nbsp;&nbsp;&nbsp;&nbsp;break;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;//不存在增广路 <img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align="top" alt="InBlock.gif">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;aug=&nbsp;0x7fff;&nbsp;&nbsp;&nbsp;&nbsp;//记录最小残留容量 <img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align="top" alt="InBlock.gif">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(&nbsp;u=pre[v=t];&nbsp;v!=s;&nbsp;v=u,u=pre[u]&nbsp;) <img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align="top" alt="InBlock.gif">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(c[u][v]&lt;aug)&nbsp;&nbsp;&nbsp;&nbsp;aug=c[u][v]; <img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align="top" alt="InBlock.gif">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(&nbsp;u=pre[v=t];&nbsp;v!=s;&nbsp;v=u,u=pre[u]&nbsp;) <img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align="top" alt="InBlock.gif">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;c[u][v]-=aug,&nbsp;c[v][u]+=aug; <img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align="top" alt="InBlock.gif">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;flow+=&nbsp;aug; <img src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif" align="top" alt="ExpandedSubBlockEnd.gif">&nbsp;&nbsp;&nbsp;&nbsp;} <img src="http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif" align="top" alt="InBlock.gif">&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;flow; <img src="http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockEnd.gif" align="top" alt="ExpandedBlockEnd.gif">} 
 </div> 
 </div> </td> 
 </tr> 
 </tbody> 
 </table></td> 
 </tr> 
 </tbody> 
</table>

转载于:https://www.cnblogs.com/ACAC/archive/2010/05/17/1737767.html