生成二进制矩阵的算法

Question

4

给定两个输入数组[R1，...，Rn]和[C1，...，Cn]。我们想要创建一个二进制矩阵A（大小为nxn），使得A的第i列元素之和为Ci，A的第j行元素之和为Rj。

我尝试使用贪心算法进行填充：从左到右填充1，并递减Ci，然后对每一行都这样做。但是，它没有奏效。（此外，然后我尝试按降序排序行和列，但仍然没有奏效）

- Mike

似乎问题定义还有更多的内容。例如，如果n为2且R1为3，则显然没有解决方案。我有一种感觉，即使每个R_i和C_i都小于n，也有很多无法解决的情况。 - user3386109

关于你的例子，我认为存在这样一个2*2矩阵{{1,2},{3,4}}。该矩阵的R1为3。 - Saurav Sahu

@SauravSahu 我不会称其为二进制矩阵。我期望一个二进制矩阵只有0或1作为它的元素。 - user3386109

1

这似乎类似于解决某些类型的Nonogram谜题，这是NP完全问题，尽管有一些技巧可以使用。 - samgak

@user3386109...明白了...是我犯了错.. :) - Saurav Sahu

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ankit Sultana · Accepted Answer

这个问题可以使用最大流解决。这个问题的一个类似但更难的版本在LightOJ上，我的参考代码可供参考。

下面是解决方案：

我们首先创建一个二分图。让行数为no_rows，列数为no_cols。

现在创建no_rows + no_cols个节点。将前no_rows个节点排列在左边（这将形成二分图的一个“partite”）。我们按照l1, l2, ..., lno_row编号这些节点。

同样，在右边排列最后的no_cols个节点（这将形成二分图的第二个“partite”）。我们按照r1、r2、...、rno_cols编号这些节点。

现在为所有1 <= i <= no_rows和1 <= j <= no_cols中的每个

和添加边缘，从左到右定向，容量为1。

现在创建一个源（S）和一个汇（T）。向左侧的每个顶点添加一个定向单位容量边缘。

类似地，从右侧的每个顶点到汇的方向添加单位容量的边缘。

现在只需在此图中找到最大流。如果某些

和某些之间存在流，则说明单元格(i, j)为1，否则为0。

注意：为了确保甚至存在这样的二进制矩阵，请确保每个边缘和边缘完全填充。

编辑：下面是C++中Dinic的实现ideone

编辑2：连接源到任何

的边缘的容量为（其中R是给定的输入数组，表示行和）。类似地，连接ri到汇的边缘的容量为（其中C是输入中表示列和的数组）。