给定两个输入数组 [R1, ..., Rn] 和 [C1, ..., Cn]。我们想要创建一个二进制矩阵 A（大小为 nxn），使得 A 的第 i 列中的元素之和为 Ci，而 A 的第 j 行中的元素之和为 Rj。
我尝试使用贪心算法填充：从左到右填充 1 并递减 Ci 并为每一行执行此操作。但是，它没有用。（另外，然后我尝试按降序对行和列进行排序，但仍然没有用）
问问题
1227 次
1 回答
6
这可以使用最大流量来解决。LightOJ上有一个类似的（这个更难的版本）问题，我的代码供参考
这是解决方案。
我们将首先创建一个二分图。设行no_rows数为 ，列数为no_cols。
现在创建no_rows + no_cols节点。排列no_rows左边的第一个节点（这将形成我们二分图的一个“部分”）。让我们将这些节点编号为l1, l2, ..., lno_row。
同样将最后一个no_cols节点排列在右侧（这将形成第二个“部分”）。让我们将它们编号为r1, r2, ... , rno_cols。
现在在每个li和 和之间
添加边，从左到右，容量为 1。rj1 <= i <= no_rows1 <= j <= no_cols
现在创建一个源（S）和一个接收器（T）。将面向源的单位容量边缘添加到左侧的每个顶点。
类似地，从右侧的每个顶点向水槽添加单位容量的边。
现在只需在此图中找到最大流量。li现在，如果 some和 some之间存在流rj，则意味着该单元格(i, j)将具有 1，否则它将具有 0。
注意：为确保甚至存在这样的二进制矩阵，请确保每个(S, l)边和(r, T)边都被完全填充。
编辑：这是 C++ ideone中 Dinic 的实现
编辑 2：将源连接到任何边缘的容量li是Ri（其中R给定的输入数组表示行总和）。ri类似地，连接到 sink的边的容量T是Ci（C输入中给出的数组表示列总和）
于 2016-08-25T07:47:31.217 回答