アルゴリズム：最大フローを使用して正しい行列値を計算する

Question

行列Nには、N×Mの行列Aがあり、N,M <= 100です。行列Aは整数値A（i、j）から成り、iとjは0 < i < Mと0 < j < Nです。私はまた、行列の "正しい"列合計と行合計を与えられます。与えられた値A（i、j）は「正しくない」（「正しい」合計に一致しない）ため、対応する「不正確さ」値B（i、j） 0からA（i、j）までである。

目的は、行列の「正しい」値C（i、j）を計算することです。ここで、C（i、j）の値は指定された行と列の合計に一致する必要があります。私は最大の流れを使わなければならないと思うが、私の試みはうまくいかない。どうすればこれを達成できますか？

Answer 1

ここでは例を挙げておきます。

matrix A: 
10 10 10 
10 10 10 
10 10 10 

matrix B: 
    2 3 4 
    5 6 4 
    3 2 1 

matrix A-B: 
    8 7 6 
    5 4 6 
    7 8 9 

だから、式A [I、J]持っている - C [I、J] < = B [I、J]を。 A [i、j] -B [i、j] < = C [i、j]に変換することができます。これは、B [i、j]がA [i、j C [i、j]より小さいか等しいものを得る。ここから、行列A-Bの項目に何かを追加する必要があることがわかります。

ここで、追加する場所と場所を見てみましょう。私はの形で物事を書いた上

c1 = 20/20 
c2 = 19/21 
c3 = 21/24 

r1 = 21/21 
r2 = 15/17 
r3 = 24/27 

：

：

(current flow through column or row)/(goal flow through column or row). 

は今のネットワークを構築しましょう

のは、次の行と列のサイズを与えられていると仮定しましょう

ここで、行の合計=合計列の合計だからあなたは '与えられた項目の合計' - '現在の項目の合計'を 's'から 't'にプッシュしようとします。

ここで、ノードが自然数によって左から右に列挙されているとしましょう。ここで、2番目のレベルのノードから3番目のレベルのノードに何かをプッシュすると、ノードiからノードjに何かをプッシュします。プッシュしたものをNewMatrix [i、j]に追加します。ここで、NewMatrixは行列ABあなたが望む行列を得ることができます。

また、行列ABでは、A [i、j]から減算してB [i、j]より小さい値を得る最小のC [i、j] C [i、j] < = B [i、j]がまだ成立していることを示しています。