使用 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}}

例如a[0][0]的值为1，最大的差异是b[0][0]的值，也就是1，所以a[0][0]的值可以改变最大 0 或 2（以及介于两者之间的所有数字，但对于此示例，我们只有 2 个选项）。

我的问题是：给定一个矩阵 a（给定总和的值无效）和一个具有最大差值的矩阵 b 可以用来满足所需的总和，如何才能我确定给定的最大差异是否有可能，以及如何获得此类矩阵的有效结果（如果存在）。

我目前的方法（行不通）：

• 制作行和列的二分图，这样每一行和每一列都有一个源、一个汇和一个节点。
• 然后将每一行连接到每一列。
• 然后将源连接到每一行。
• 然后将每列连接到水槽。
• 将从源到每个行节点的边的容量设置为 Math.Abs（a 中的当前数字总和 - a 中给定的数字总和（为此行)).
• 从每个列节点到汇点的边也相同（但这次是列总和）。
• 相应地将每个单元格的行到列的节点之间的容量设置为 b 中给定的最大差异。
• 使用 Ford Fulkerson 确定最大流量。

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

Answer 1

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

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

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

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

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

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

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