算法:使用最大流量计算正确的矩阵值

Question

我给定的与大小为N×M个的矩阵A N,M <= 100.矩阵A由整数值A(i,j)组成,其中i和j是 0 < i < M和0 < j < N.我也得到矩阵的"正确"列和和行和.给定值A(i,j)是"不正确"(它们与"正确"总和不匹配)因此我们提供相应的"不正确"值B(i,j),其中B(i,j)范围从0到A(i,j).

目标是计算矩阵中的"正确"值C(i,j),其中A(i,j) - C(i,j) =< B(i,j),C(i,j)值也必须与给定的行和列和相匹配.我想我必须使用最大流量,但我的尝试没有奏效.我怎样才能做到这一点？

Answer 1

我在这里只给你举一个例子。

matrix A:
 10 10 10
 10 10 10
 10 10 10

matrix B:
  2  3  4
  5  6  4
  3  2  1

matrix A-B:
  8  7  6
  5  4  6
  7  8  9

所以你有公式 A[i,j] - C[i,j] <= B[i,j]。您可以将其转换为 A[i,j] - B[i,j] <= C[i,j] 这意味着 B[i,j] 是您需要从 A[i,j 中减去的最小的东西] 得到小于或等于 C[i,j] 的值。从这里您知道需要向矩阵 AB 中的条目添加一些内容。

现在让我们找出要添加的内容和位置。

假设您获得以下行和列大小：

c1 = 20/20
c2 = 19/21
c3 = 21/24

r1 = 21/21
r2 = 15/17
r3 = 24/27

上面我写的内容是这样的：

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

现在让我们构建一个网络：

现在请注意，行的总和 = 列的总和。因此，您尝试将“给定条目总和”-“当前条目总和”从“s”推到“t”。

现在，我们假设节点是按自然数从左到右枚举的。现在，当您将某些内容从第二级节点推送到第三级节点时，例如，将某些内容从节点 i 推送到节点 j，您还会将推送的内容添加到 NewMatrix[i,j]，其中 NewMatrix 是矩阵 AB然后你就得到了你想要的矩阵。

另请注意，一开始，在矩阵 AB 中，您必须从 A[i,j] 中减去最小的 C[i,j] 才能得到小于或等于 B[i,j] 的值，现在你在 C[i,j] 上添加了一些东西，不等式 A[i,j]-C[i,j]<=B[i,j] 仍然成立。