我正在尝试在C中实现匈牙利算法。
我有一个矩阵：
在这里，零撇号是指定的零。然后，按照维基百科以下的说明，我标记第4行（未分配的零），第1列（带有未分配的零的列），然后标记第2行（在标记列中有零的行）。
因此，这表明要涵盖所有零所需的最小线数为：
这段代码选择哪些零是零素数（指定零）。
然后，该代码标记所有在新标记列中具有指定的行：
但是这个解释（以及维基百科的解释）不能解释我上面的矩阵。为什么？
我有一个矩阵：
35 0 0 0
0 30 0 5
55 5 0 10
0 45 30 45
我现在需要找到覆盖所有零的最小行数（尽可能多地进行分配）。显然，通过检查，这是第1列和第3列以及第1行。
- 第1行有三个零：选择任意一个（我选择第一个）并进行分配
- 第2行：分配第一个零
- 第3行：分配第三个零
- 第4行未分配（因为唯一的零位于已经有分配零的列中）
如果我按照上述方法对我的矩阵进行操作，结果如下：
35 0' 0 0
0' 30 0 5
55 5 0' 10
0 45 30 45
在这里，零撇号是指定的零。然后，按照维基百科以下的说明，我标记第4行（未分配的零），第1列（带有未分配的零的列），然后标记第2行（在标记列中有零的行）。
因此，这表明要涵盖所有零所需的最小线数为：
+--------
|
+--------
|
但是这并没有命中 (2, 3) 的零。相关的 C 代码：
for (i = 0; i < M->size; i++) {
for (j = 0; j < M->size; j++) {
if (M->values[i][j] == 0) {
if (assigned_cols[j] == 0) {
assigned_cols[j] = 1; // We've assigned something in this col
assigned_rows[i] = 1; // We've assigned something in this row.
marked_rows[i] = 0;
total--;
break; // Go to the next row
} else {
marked_cols[j] = 1; // Then there exists a zero in this col in an unassigned row
mark_col(M, j); // marks all elements in column j
total++;
}
}
}
}
这段代码选择哪些零是零素数（指定零）。
然后，该代码标记所有在新标记列中具有指定的行：
for (i = 0; i < M->size; i++) {
if (marked_cols[i] == 1) {
for (j = 0; j < M->size; j++) {
//iterating through rows
if (M->values[j][i] == 0) {
// then (j,i) is a zero in a marked col
// mark the row
if (marked_rows[j] != 1) {
total++;
marked_rows[j] = 1;
}
break; // no need to continue more
}
}
}
}
但是这个解释（以及维基百科的解释）不能解释我上面的矩阵。为什么？