4,10/ 1,7) ③2,5)(6,2)(2,4) (1,8） (3,10) (a)费用、容量网络 图7-17 (c)可行流f'：f5 (4)构造关于f'的有向费用网络W(f),如图7-17(d)所示。 (⑤)可求得W(f1)的最短路为： 巴，→→4，图中以双线表赤。在原 2 网络图中与这条最短路相应的增广链 {,24,}上，对流量v(f)进行调整， 调整量0min{10,7-5}2,从而 得新的最小费用流f2,其流量： (d)费用网络W(f') (f2)=7,如图7-17(e)所示。 图7-17s （2，5）（6，2）（2，4） ○ （1，7） （3，10） ○3 ○4 （a）费用、容量网络 s 2 5 0 0 ○ 5 ○3 0 ○4 （c） 可行流 f 1 ：v(f 1 )=5 5 0 图7-17 ○2 ○t ○ ○t ⑷构造关于f 1的有向费用网络W（f 1），如图7-17（d）所示。 （4，10） （1，8） s 2 -2 6 2 ○ 1 ○3 3 ○4 （d）费用网络W(f 1 ) 1 4 ○ ○t -1 -1 图7-17 ⑸可求得W（f 1）的最短路为： vs →v2 →vt ，图中以双线表示。在原 网络图中与这条最短路相应的增广链 ｛vs v2 vt ｝上，对流量v(f 1 )进行调整， 调整量θ= min｛10，7-5｝=2，从而 得新的最小费用流 f 2 ，其流量： v(f 2 )=7，如图7-17（e）所示