我正在尝试在 C 中实现匈牙利算法。
我有矩阵：
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
}
}
}
}
但这（和维基百科的解释）对于我上面的矩阵失败了。怎么来的？