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

建模

解： (1)对所有 ( x, y ) ∈ E ,令 f ( x, y ) = 0 ,如图 a 各边的第二个数。 标 s 为 ( s + , ∞) ,令 δ s = ∞ 。

(2)对 s 的邻接点 a 标 ( s + ,3) 。这里因 s 指向 a,故标 s 的上标为+,又 δ a = min{c( s, a) f ( s, a), δ s } = min{3 0, ∞} = 3同理对 s 的邻接点 b 标 ( s + , 4) 。如图 a( s+,3) a 3, 0 5, 0

c3, 0

s ( s+, ∞)4

5, 0

2, 0

1, 0 5, 0

t

b ( s + , 4)

3, 0

d

(a)

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