建模
解： (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)