Ford Fulkersonを使用して二分グラフの最大流量を計算し、合計に達する値を決定する

Question

この状況でFord Fulkersonアルゴリズムをどのように使うべきかを判断しようとしています。整数値を含む行列aがあります。各行の最後の列と最後の行には、行/列全体の合計が含まれます。

例：

int[][] a = {{1, 3, 5, 9}, 
      {4, 2, 1, 7}, 
      {5, 5, 6, *}} // * Is not determined since the sums 
          // * do not count as summable values. 

このことは、マトリックス内の値は必ずしも正しくないこと、です。合計の値は、例えば、常に正しいではありません。

int[][] a = {{1, 3, 3, 9}, 
      {2, 3, 1, 7}, 
      {5, 5, 6, *}} // * Is not determined since the sums do 
          // * not count as summable values. 

セルが与えられた合計値を満たすことができ、最大差を含むマトリックスbがあります。例えば

int[][] b = {{1, 0, 3}, 
      {2, 1, 2}} 

例えば1 a[0][0]の値、のために、最大の違いは、1である、b[0][0]での値であるので、a[0][0]の値は0または2最大値に変更（およびすべてことができますその間の数字ですが、この例では2つのオプションしかありません）。

私の質問は：与えられた合計で無効な値を持つaと与えられた合計を満たすために使用できる最大の差を持つ行列bが与えられているとします。最大の差異、そしてそのようなマトリックスの有効な結果を得る方法はありますか？

私の現在のアプローチ（ない作品）：

• は、ソース、シンク及び各行と列のノードを持っているので、行と列の二部グラフを作ります。
• 次に、各行を各列に接続します。
• 次に、ソースを各行に接続します。
• 次に、各列をシンクに接続します。
• ソースから各行ノードまでのエッジの容量をMath.Abs​​に設定します（aの現在の合計 - a（その行について）の数値の合計）。
• 各列ノードからシンクまでのエッジと同じです（ただし、今回は列合計）。
• 行と列のノード間の容量を、各セルの対応する最大差bに設定します。
• Ford Fulkersonを使用して最大流量を決定します。

アルゴリズムの結果を使用して、行列aの各値が各行と列に合うように正しい値を決定する方法を知りません。

Answer 1

だから私はこの問題への解決策を自分で見つけ： - 各I、jためBあなたが値行列A[i][j]と違い行列B[i][j]を持っている場合は

、あなたはAを減算する必要があるだろう。次に、行を左ノードとして使用し、列を右ノードとして使用して二部グラフを作成する必要があります。

これで、各行ノードを列ノードに接続する必要があります（逆も同様です）。また、ソースをすべての行ノードに接続し、すべての列ノードをシンクに接続します。

ソースから行ノードまでの各エッジの容量は、現在の数値の合計であり、同じことが、列ノードのエッジ・キャプチャがシンクするためのものです。

行ノードと列ノードの間の各容量は、現在のB[i][j] * 2です。完全なネットワークが必要です。

Ford FulkersonとEdmonds Karpを使用してください。各行ノードと列ノードの間のフローは、現在のA[i][j]まで加算されるべき数です。

結果のA行列があなたの答えになります。