使用Ford Fulkerson确定足以求和的值的二分图中的最大流量

Question

我想弄清楚在这种情况下我应该如何使用福特富尔克森算法这种情况有点像数独.我们有一个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}}

例如,对于值a[0][0]1,最大差值是at b[0][0],即1,因此值at a[0][0]可以更改为0或2最大值(以及介于两者之间的所有数字,但对于此示例,我们只有2个选项).

我的问题是:给定一个矩阵a(给定总和的值无效)和一个b可以用来满足所需总和的最大差值的矩阵,如何确定在给定的最大差异下它甚至是可能的,我该如何得到这种矩阵的有效结果(如果存在的话).

我目前的做法(不起作用):

• 制作行和列的二分图,因此每个行和列都有一个源,一个接收器和一个节点.
• 然后将每行连接到每列.
• 然后将源连接到每一行.
• 然后将每列连接到接收器.
• 将从源到每个行节点的边的容量设置为Math.Abs​​(当前的数字a总和 - 给定a(对于该行)的数字总和).
• 从每个列节点到接收器的边缘相同(但是此时列的总和).
• 将行的节点之间的容量设置b为相应的每个单元格的给定最大差异.
• 使用Ford Fulkerson确定最大流量.

我不知道如何使用我的算法结果来确定矩阵的正确值,a以满足每行和每列的给定总和.

Answer 1

所以我自己找到了解决这个问题的方法：

如果您有值矩阵A[i][j]和差异矩阵B[i][j]，则必须为每个,减去A- 。然后，您必须使用行作为左节点、列作为右节点来创建二部图。BIj

然后，您必须将每个行节点连接到列节点，反之亦然。还将源连接到所有行节点，并将所有列节点连接到接收器。

从源节点到行节点的每条边的容量是当前数字之和，列节点的边容量也是如此。

row-node和column-node之间的每个容量都是当前B[i][j]* 2。那么你应该有一个完整的网络。

使用福特·富尔克森和埃德蒙兹·卡普。每个行节点和列节点之间的流量是应该加到当前的数字A[i][j]。

你得到的A矩阵将是你的答案。