第2讲 最大流与最小费用流(16)

建模

(B)增流过程 (i)令 u = t 。 ,则 f (v, u ) = f (v, u ) + δ t ;若 u 的 (ii)若 u 的标号为 (v + , δ t ) ) 标号为 (v , δ t ) ,则 f (u , v) = f (u , v) δ t 。 。否 (iii)若 u = s ,把全部标号去掉，并回到标号过程(A) 则，令 u = v ,并回到增流过程(ii) 。 注： 1 (1)标号 ( x + , δ y ) 表示从 x 流入 y 的流可增加 δ y ; ( x , δ y ) 表示从 y 流入 x 的流可减少 δ y ; s + , ∞) 表示发点可提供任意多的流 ( 到别的点。 (2)算法终止后，令已标号的点的集合为 A ,则割 ( A, A) 即为 最小割，从而最大流的流量 Val f = C ( A, A) 。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库第2讲 最大流与最小费用流(16)在线全文阅读。