c# - Max flow in bipartite graph using Ford Fulkerson to determine values to suffice to sum -

i'm trying figure how should use ford fulkerson algorithm in situation situation kinda sudoku-like. have matrix a contains integer values. last column of each row , last row of each column, contains sum of entire row / column.

example:

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

this thing is, values within matrix not correct. values sum not correct, example:

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

there matrix b contains max difference cell can have meet given sum. example

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

for example value of a[0][0], 1, max differences value @ b[0][0], 1, value @ a[0][0] can changed 0 or 2 maximum (and numbers in between, example have 2 options).

my question is: given matrix a (with invalid values given sum) , matrix b max differences can used meet required sum, how can determine wether it's possible given maximum differences , how valid result of such matrix (if exists).

my current approach (which not works):

• make bipartite graph of rows , columns, have source, sink , node each row , column.
• then connect each row each column.
• then connect source each row.
• then connect each column sink.
• set capacities edges source each row-node math.abs(current sum of numbers in a - given sum of numbers in a (for row)).
• same edges each column-node sink (but column sums time).
• set capacities between nodes rows columns given max differences in b each cell accordingly.
• use ford fulkerson determine max flow.

i don't know how should use results of algorithm determine correct values matrix a meet given sum each row , column.

so found solution problem myself:

if have values matrix a[i][j] , differences matrix b[i][j], you'd have substract a - b each i, j. have create bipartite graph using rows left nodes , columns right nodes.

you have connect each of row nodes column nodes , vice versa. connect source row nodes , connect column nodes sink.

the capacity each edge source row node current sum of numbers , same goes edge capaties of column nodes sink.

each capacity between row-node , column-node current b[i][j] * 2. should have complete network.

use ford fulkerson edmonds karp. flow between each row-node , column-node number should added current a[i][j].

your resulting a matrix answer.