我已经在C++中实现了匈牙利算法。这个实现对于许多情况都非常有效。然而，有些情况下我的算法根本不起作用，因为我相信（并且事实证明）算法的一个步骤实现是错误的。
我的实现将数组X作为输入，运行算法的步骤，并产生最终的分配方案。
算法的步骤可以在维基上找到：匈牙利算法 在第3步中，它有以下成本数组（工人由行表示，工作由列表示）。
然而我不明白什么是正确的实现方式。如何分配尽可能多的任务？选择是随机的吗？那么，如果选择是随机的，我可以选择第一个工人来完成第一项工作，第二个工人来完成第四项工作，第四个工人来完成第二项工作。这样第二个工人就被排除了。但是在维基百科中，作者采取了不同的方法。第三个工人必须完成第一项工作，第二个工人必须完成第二项工作，第四个工人必须完成第二项工作。所以第一个工人被排除了。
如果我随机将第三份工作分配给第一名工人，将第四份工作分配给第二名工人，然后将第一份工作分配给第三名工人，那么第四名工人将被排除在外。但是为了使算法正常运行，我们需要尽可能地为工人分配工作。这种情况是这样吗？不是的，因为如果我将第一份工作分配给第四个工人而不是第三个工人，我就可以将第二份工作分配给第三个工人，从而算法不仅会尽可能地为工人分配工作，而且会找到最佳结果。
通过采用这种方法，我们可以发现以前的情况得到了解决。我们做的是，将第三项工作分配给第一项工人，将第四项工作分配给第二项工人，然后我们看到第三项工人可以接受2项工作，所以我们暂时忽略他，将第一项工作分配给第四项工人，然后按顺序返回，将第二项工作分配给第三项工人。
我的实现遵循了这个逻辑，但是却不能解决所有情况。
例如，我们来看以下案例：
第一个工人可以接受4个任务，第二个4个，第三个2个，第四个2个。因此，我的实现没有分配任务，因为我需要至少一个只能接受一个任务的工人才能进行任务分配，然后通过重新扫描表格继续执行。 那么在这种情况下我该怎么办呢？任意的任务分配是不好的选择，不幸的是，在那次讲座中没有提出任何建议。 我只能想到以下方法： 对于每个工人，都有一个计数器，其值表示可以分配给他的任务数量，那么在该行中有多少个零？这就是计数器的值。 然后开始将任意任务分配给计数器最小的工人。因此，在这种情况下，每个工人的计数器数组将包括以下值：
我会选择第三个工人，并将第一个工作随意分配给他。新的计数器将是：
最后，我会把第四项任务交给第一份工作。
因此，最终的任务如下：
这似乎是一种不错的方法，但我担心可能存在一些特殊情况，这种方法可能行不通。我该如何验证这种方法是否适用于所有情况？如果不适用，有什么方法可以完全解决我的问题呢？
提前感谢您的帮助。
我的实现将数组X作为输入，运行算法的步骤，并产生最终的分配方案。
算法的步骤可以在维基上找到：匈牙利算法 在第3步中，它有以下成本数组（工人由行表示，工作由列表示）。
然后它说
Initially assign as many tasks as possible then do the following
然而我不明白什么是正确的实现方式。如何分配尽可能多的任务？选择是随机的吗？那么，如果选择是随机的，我可以选择第一个工人来完成第一项工作，第二个工人来完成第四项工作，第四个工人来完成第二项工作。这样第二个工人就被排除了。但是在维基百科中，作者采取了不同的方法。第三个工人必须完成第一项工作，第二个工人必须完成第二项工作，第四个工人必须完成第二项工作。所以第一个工人被排除了。
这样随意行动的问题在于以下情况：
假设在我们对输入进行算术运算并分配尽可能多的任务给工人之前，我们有以下成本矩阵：
2 2 0 3
6 1 6 0
0 0 6 1
0 3 5 3
如果我随机将第三份工作分配给第一名工人，将第四份工作分配给第二名工人，然后将第一份工作分配给第三名工人，那么第四名工人将被排除在外。但是为了使算法正常运行，我们需要尽可能地为工人分配工作。这种情况是这样吗？不是的，因为如果我将第一份工作分配给第四个工人而不是第三个工人，我就可以将第二份工作分配给第三个工人，从而算法不仅会尽可能地为工人分配工作，而且会找到最佳结果。
结论: 随机分配不是一个好方法。
我搜索了一下，发现了以下讲座:
http://www.youtube.com/watch?v=BUGIhEecipE
在这个讲座中，教授提出了一种不同的方法来解决尽可能多地分配任务的问题。如果任何一行或一列恰好有一个零，我们将进行分配。因此，从第一行开始，您需要检查第一行是否只有一个零，如果是这种情况，则进行分配。否则，请忽略该行并转到第二行，通过重新扫描表格重复执行相同的操作，直到由于分配而覆盖所有零。通过采用这种方法，我们可以发现以前的情况得到了解决。我们做的是，将第三项工作分配给第一项工人，将第四项工作分配给第二项工人，然后我们看到第三项工人可以接受2项工作，所以我们暂时忽略他，将第一项工作分配给第四项工人，然后按顺序返回，将第二项工作分配给第三项工人。
我的实现遵循了这个逻辑，但是却不能解决所有情况。
例如，我们来看以下案例：
0 0 0 0
0 0 0 0
0 0 4 9
0 0 2 3
第一个工人可以接受4个任务，第二个4个，第三个2个，第四个2个。因此，我的实现没有分配任务，因为我需要至少一个只能接受一个任务的工人才能进行任务分配，然后通过重新扫描表格继续执行。 那么在这种情况下我该怎么办呢？任意的任务分配是不好的选择，不幸的是，在那次讲座中没有提出任何建议。 我只能想到以下方法： 对于每个工人，都有一个计数器，其值表示可以分配给他的任务数量，那么在该行中有多少个零？这就是计数器的值。 然后开始将任意任务分配给计数器最小的工人。因此，在这种情况下，每个工人的计数器数组将包括以下值：
4
4
2
2
我会选择第三个工人，并将第一个工作随意分配给他。新的计数器将是：
3
3
0
1
我会选择第四个工人并为他安排唯一可用的任务(即第二项工作)。新柜台将是:
2
2
0
0
然后我可以选择第一个工人或第二个工人。对于第一个工人，我会进行任意分配，并将第三项工作交给他。计数器将是
1
0
0
0
最后，我会把第四项任务交给第一份工作。
因此，最终的任务如下：
0 0 0 *
0 0 * 0
* 0 4 9
0 * 2 3
这似乎是一种不错的方法，但我担心可能存在一些特殊情况，这种方法可能行不通。我该如何验证这种方法是否适用于所有情况？如果不适用，有什么方法可以完全解决我的问题呢？
提前感谢您的帮助。