将数字 1 排列在二维矩阵中

给定二维矩阵的行数和列数

初始矩阵所有元素均为0

给定每行中应该出现的 1 的数量

给定每列中应该出现的 1 的数量

确定是否可以形成这样的矩阵。

例子：

Input: r=3 c=2 (no. of rows and columns)
2 1 0 (number of 1's that should be present in each row respectively)
1 2 (number of 1's that should be present in each column respectively)

输出：可能

解释：

1 1
0 1
0 0

我尝试解决这个问题大约 12 个小时，通过检查 Ri 的总和 = Ci 的总和

但我想知道对于像这样的情况是否不可能

3 3
1 3 0
0 2 2

r 和 c 最大可达 10^5

有什么想法我应该如何进一步采取行动？

编辑：添加的约束和输出应该只是“可能”或“不可能”。不需要显示可能的矩阵。

现在有人可以帮助我吗？

提示：一种可能的解决方案通过创建一个特殊的图并在其上运行标准的最大流算法来利用最大流问题。

如果您不熟悉上述问题，您可以开始阅读相关内容，例如这里https://en.wikipedia.org/wiki/Maximum_flow_problem https://en.wikipedia.org/wiki/Maximum_flow_problem

如果您对完整的解决方案感兴趣，请发表评论，我将更新答案。但这需要理解上面的算法。

按要求解决：

创建一个图表r+c+2 nodes.

节点0是源节点r+c+1是水槽。节点1..r代表行，而r+1..r+c列。

创建以下边：

• 从源头到节点i=1..r容量r_i
• 从节点i=r+1..r+c容量下沉c_i
• 所有节点之间i=1..r and j=r+1..r+c容量 1

运行最大流算法，行节点和列节点之间的饱和边定义了应该在哪里放置 1。

或者，如果不可能，则最大流量值小于矩阵中的预期流量值。