于是 δ.∑w(u,)<0 (a,v∈A(C) 令∫=∫+f,由引理941知 Valf =val+alfc =vals=vo ()=1(f)+v()<1() 可见∫不是N的最小费用v值流,矛盾。 充分性:设N()不含负费用圈,广是N中任一个流值为vo的可行流,则由引理942,N(f) 中存在可行流∫'使得∫”=f+∫ (1)如果f是N()中的零流,则f”=f,w(”)=v(f)。 (2)如果∫不是N()中的零流,则由引理941知 f '=valf-valf 0 从而由引理944 f"=J+JC2+…+Jc 其中f为N(O)中的圈流,(=12,…k),故 f)=∑w(′C 因N(O)不含负费用圈,故w(′c,)≥0(=1,2,…,k),故由引理941, v()=w(f)+()≥w(f) 由(1)、(2)知,∫为N中的最小费用vo值流。证毕 由定理941可得,求最小费用v值流的负费用圈算法: Step1:在N中运行最大流算法,增流时取δ=min{4(P)v-∫}。要么求出流值为v的可行流f 转Step2;要么判定N中不存在流值为w的可行流。停止。 Step2:构造增量网络N(∫),在N(∫)中找负费用有向圈。如果不存在负费用有向圈,则结束,当前 ∫为最小费用w值流;否则,找到一个负费用有向圈C,转Step3 Step3:求C上的最小容量δ,构造N()的圈流fc,令∫:=∫+fc,转Step2 例:求下列网络中从x到y的流值为3的最小费用流 (3,4) (1,1) 网络N,每条弧上的三元数组分别表示f(c,w)。于是 (,) ( ) ( ) (,) 0 C uv AC w f w uv δ ∈ ′ ′ = ⋅ < ∑ 。 令 * C f = + f f  ，由引理 9.4.1 知 * Val f Val f Val f Val f v =+ == C 0 . * ( ) () ( ) () wf wf w f wf C =+ < ′ . 可见 f 不是 N 的最小费用 v0值流，矛盾。 充分性：设 N f ( ) 不含负费用圈， * f 是 N 中任一个流值为 v0 的可行流，则由引理 9.4.2， N f ( ) 中存在可行流 f ′使得 * f = f f + ′, （1）如果 f ′是 N f ( ) 中的零 流，则 * * f = = f wf wf , ( ) () 。 （2）如果 f ′不是 N f ( ) 中的零 流，则由引理 9.4.1 知 * 0 0 Val f Val f Val f v v ′ = − =−= 0 , 从而由引理 9.4.4 CC C 1 2 k f ′ = ff f + +…+ ， 其中 Ci f 为 N f ( ) 中的圈流，(i = 1,2, …, k )，故 1 () ( )i k C i wf wf = ′′ ′ = ∑ 。 因 N f ( ) 不含负费用圈，故 ( ) 0 ( 1, 2, , ) Ci wf i k ′ ≥ =… ，故由引理 9.4.1， * wf wf w f wf ( ) () ( ) () =+ ≥ ′ ′ 由(1)、(2)知，f 为 N 中的最小费用 v0值流。证毕。 由定理 9.4.1 可得，求最小费用 v0值流的负费用圈算法： Step 1：在 N 中运行最大流算法，增流时取 min{ ( ), } 0 δ = Δ − f Pv f 。要么求出流值为 v0的可行流 f， 转 Step 2；要么判定 N 中不存在流值为 v0的可行流。停止。 Step 2：构造增量网络 N f ( ) ，在 N f ( ) 中找负费用有向圈。如果不存在负费用有向圈，则结束，当前 f 为最小费用 v0值流；否则，找到一个负费用有向圈 C，转 Step 3。 Step 3：求 C 上的最小容量δ ，构造 N f ( ) 的圈流 Cf ， 令 : C f = f f + ，转 Step 2。 例：求下列网络中从 x 到 y 的流值为 3 的最小费用流。 网络 N，每条弧上的三元数组分别表示 f, (c, w)。 (2,2) (2,3) (3,4) (1,1) (3,1) (2,5) ,(3,2) x y