Algorithms: using maximum flow to calculate correct matrix values

Question

I have been given a matrix A with size N x M with N,M <= 100 . Matrix A consists of integer values ​​A (i, j), where i and j 0 < i < M and 0 < j < N . They also give me the "correct" sums of columns and the sums of the rows of the matrix. The indicated values ​​of A (i, j) are "incorrect" (they do not correspond to the "correct" sums), and therefore we are given the corresponding values ​​of the "incorrectness" B (i, j), where B (i, j) ranges from 0 to A (i, j).

The goal is to calculate the “correct” values ​​of C (i, j) in the matrix, where A(i,j) - C(i,j) =< B(i,j) values ​​of C (i, j) also must match the given sum of rows and columns. I think I need to use the maximum thread, but my attempts did not work. How can I achieve this?

Answer 1

I will just give an example here.

 matrix A: 10 10 10 10 10 10 10 10 10 matrix B: 2 3 4 5 6 4 3 2 1 matrix AB: 8 7 6 5 4 6 7 8 9 

So, you have the formula A [i, j] - C [i, j] <= B [i, j]. You can convert it to [i, j] - B [i, j] <= C [i, j], which means that B [i, j] is the smallest thing you need to subtract from A [i, j ] to get something less than or equal to C [i, j]. From here you know that you need to add something to the elements of the matrix AB.

Now find what and where to add.

Suppose you are given the following row and column sizes:

 c1 = 20/20 c2 = 19/21 c3 = 21/24 r1 = 21/21 r2 = 15/17 r3 = 24/27 

Above, I wrote things in the form:

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

Now create a network:

Now notice that the total amount of rows = the total amount of columns. Thus, you are trying to press "preset record amount" - "current record amount" from "s" to "t".

Now suppose that the nodes are listed from left to right by natural numbers. Now, when you push something from a second level node to a third level node, let's say you push something from node i to node j, you also add everything you click on NewMatrix [i, j], where NewMatrix - matrix AB, and you get the desired matrix.

Also note that at the beginning in the matrix AB you had the smallest C [i, j] that you had to subtract from A [i, j] to get something less than or equal to B [i, j], and now that you have added something to this C [i, j], the inequality A [i, j] -C [i, j] <= B [i, j] still holds.