c# - 使用 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]，则必须减去 A - B 用于每个 I，j。然后，您必须使用行作为左节点，列作为右节点来创建二分图。

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

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

行节点和列节点之间的每个容量是当前B[i][j] * 2。那么你应该有一个完整的网络。

将 Ford Fulkerson 与 Edmonds Karp 一起使用。每个行节点和列节点之间的流是应该添加到当前 A[i][j] 的数字。

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