math - 在给定行和列总和的情况下查找二进制矩阵是否存在

Question

如何找出是否可以构造具有给定行和列和的二进制矩阵。

输入 ：

输入的第一行包含两个数字 1≤m,n≤1000，即矩阵的行数和列数。下一行包含 m 个数字 0≤ri≤n – 矩阵中每一行的总和。第三行包含 n 个数字 0≤cj≤m – 矩阵中每一列的总和。

输出：

如果存在 m×n 矩阵 A，则输出“YES”，每个元素为 0 或 1。否则为“NO”。

我尝试阅读有关断层扫描算法的内容，但无法找到答案，因为与断层扫描算法相关的所有论文都非常复杂。

有人可以帮帮我吗..

Answer 1

我已经使用基于网络流的建模成功地实现了为 R 随机生成此类矩阵。我打算有一天把这些想法写下来，但还没有找到时间。为此，我阅读了 Miklós 和 Podani的Randomization of Presence-absence Matrices: Comments and New Algorithms ：

Havel - Hakimi定理 ( Havel 1955 , Hakimi 1962 ) 指出存在一个矩阵X _n,m由 0 和 1 组成，行总计a ₀ =( a ₁ , a ₂ ,... , a _n ) 和列总计b ₀ = ( b ₁ , b ₂ ,… , b _m ) 使得b _i ≥ b _{i +1}对于每个 0 < i < m当且仅当另一个矩阵X _{n -1, m}个 0 和 1，行总计a ₁ =( a ₂ , a ₃ ,... , a _n ) 列总计b ₁ =( b ₁ -1, b ₂ -1,... , b _{a 1} -1, b _{a 1 +1} ,… , b _m ) 也存在。

我想这应该是递归决定你的问题的最佳方法。

用我自己的话来说：选择任意一行，将其从总数列表中删除。调用删除的数字k。还要从总和较大的k列中减去 1 。你得到一个较小矩阵的描述，然后递归。如果在任何时候您都没有k列的和非零，那么就不会存在这样的矩阵。否则，您可以使用相反的过程递归地构建匹配矩阵：获取递归调用返回的矩阵，然后再添加一行，其中包含k个，放置在您最初从其计数中减去 1 的列中。

执行

bool satisfiable(std::vector<int> a, std::vector<int> b) {
  while (!a.empty()) {
    std::sort(b.begin(), b.end(), std::greater<int>());
    int k = a.back();
    a.pop_back();
    if (k > b.size()) return false;
    if (k == 0) continue;
    if (b[k - 1] == 0) return false;
    for (int i = 0; i < k; i++)
      b[i]--;
  }
  for (std::vector<int>::iterator i = b.begin(); i != b.end(); i++)
    if (*i != 0)
      return false;
  return true;
}