最小費用最大流算法:最小費用最大流的例題[朗讀]

可以採用對偶法以費用c為權通過福德算法先找從起點至終點的最短路,再以該最短路為增廣鏈調整流量,每一次調整都以矩陣a記錄調整的結果.為了能夠滿足增廣鏈上正向弧非飽合、逆向弧非零流的條件,在每一次以c為權尋找最短路之前,對費用c矩陣進行調整.將正向飽合弧、逆向零流弧對應的c值設為無窮大,非飽合弧的c值設為初始值,這樣一來,計算出的最短路徑增廣鏈就不會包括正向飽合弧與逆向零流弧了。