5

我试图弄清楚在这种情况下我应该如何使用福特富尔克森算法这种情况有点像数独。我们有一个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]可以将 at 的值更改为最大 0 或 2（以及介于两者之间的所有数字，但对于此示例，我们只有2 个选项）。

我的问题是：给定一个矩阵a（给定总和的值无效）和一个b具有最大差异的矩阵，可用于满足所需的总和，我如何确定在给定的最大差异下是否有可能，我该怎么做得到这样一个矩阵的有效结果（如果存在的话）。

我目前的方法（不起作用）：

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

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

4

1 回答 1

4

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

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

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

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

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

使用福特富尔克森和埃德蒙兹卡普。每个 row-node 和 column-node 之间的流是应该加到 current 的数字A[i][j]。

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

于 2016-04-11T00:58:12.733 回答