2 (1,7） (4,10) (2,5)(6,2)(2,4) (1,8) 3 (3,10) (e)可行流f2:v(f2)=7 (a)费用、容量网络 图7-17 (6)构造关于f的有向费用网络W(f2),如图7-17()所示。 (7)可求得W(f2)的最短路为： →→v4→，图中以双线表示。在原 2 网络图中与这条最短路相应的增广链 {飞，Vv,}上，对流量v(f2)进行调整 4 调整量0-min(8-5,10,4}3;从 而得新的最小费用流f，其流量： (f)费用网络W(f2) v(f3)=10,如图7-17(g)所示。 图7-17 s 2 5 0 0 ○ 7 ○3 0 ○4 5 2 ○ ○t （e） 可行流 f 2 ：v(f 2 )=7 s （2，5）（6，2）（2，4） ○ （1，7） （3，10） ○3 ○4 （a）费用、容量网络 ○2 ○t （4，10） （1，8） 图7-17 ⑹构造关于f 2的有向费用网络W（f 2），如图7-17（f）所示。 s 2 -2 6 2 ○ ○3 3 ○4 （f）费用网络W(f 2 ) 1 4 ○ ○t -1 -1 -4 ⑺可求得W（f 2）的最短路为：vs →v3 →v4 →vt ，图中以双线表示。在原 网络图中与这条最短路相应的增广链 ｛vs v3 v4 vt ｝上，对流量v(f 2 )进行调整， 调整量θ= min｛8-5，10，4｝=3，从 而得新的最小费用流 f 3 ，其流量： v(f 3 )=10，如图7-17（g）所示。 图7-17