我已经阅读了这里的所有答案、Wikipedia 和 WikiHow、印度人的讲座以及其他来源，我很确定我理解他们在说什么，并以这种方式实现了它。但我对所有这些解释都表明这显然是错误的说法感到困惑。
他们都说用最少的行数覆盖矩阵中的零点，如果等于 N（也就是说，每一行和每一列都有一个零），那么就有一个零解，我们就完成了。但后来我发现了这个：
a b c d e
A 0 7 0 0 0
B 0 8 0 0 6
C 5 0 7 3 4
D 5 0 5 9 3
E 0 4 0 0 9
每一行每一列都有一个零，没有办法用少于五行来覆盖零，但显然没有零解决方案。C 行在 b 列中只有零，但 D 行没有零。
我在这里误解了什么吗？我是否需要更好的测试来确定是否可以进行零分配？所有这些来源都遗漏了一些重要的东西吗？
您可以仅用四行覆盖示例中矩阵中的零点：b 列、A 行、B 行、E 行。
以下是该算法的分步演练，该算法在6 月 25 日的 Wikipedia 文章中出现，应用于您的示例：
a b c d e
A 0 7 0 0 0
B 0 8 0 0 6
C 5 0 7 3 4
D 5 0 5 9 3
E 0 4 0 0 9
第一步：每一行的最小值为零，所以减法没有效果。我们尝试分配任务，使每项任务都以零成本执行，但事实证明这是不可能的。继续下一步。
第二步：每一列的最小值也为零，所以这一步也没有效果。继续下一步。
第 3 步：我们找到最少数量的行来覆盖所有的零。我们找到 [b,A,B,E]。
a b c d e
A ---|---------
B ---|---------
C 5 | 7 3 4
D 5 | 5 9 3
E ---|---------
第 4 步：我们找到最小的未覆盖元素。这是 3，在 (C,d) 和 (D,e)。我们从每个未标记的元素中减去 3，并为两行覆盖的每个元素添加 3：
a b c d e
A 0 10 0 0 0
B 0 11 0 0 6
C 2 0 4 0 1
D 2 0 2 6 0
E 0 7 0 0 9
立即覆盖所有零的最小行数变为 5。这很容易验证，因为每一行都有一个零，每列都有一个零。该算法断言，我们在步骤 1 中寻找的分配现在应该可以在新矩阵上进行。
我们尝试分配任务，使每个任务都以零成本执行（根据新矩阵）。现在这是可能的。我们找到解 [(A,e),(B,c),(C,d),(D,b),(E,a)]。
我们现在可以返回并验证我们找到的解决方案实际上是最优的。我们看到每个分配的工作都有零成本，除了 (C,d)，它的成本为 3。由于 3 实际上是矩阵中最低的非零元素，我们已经看到没有零成本解决方案，很明显这是一个最优解。