二维矩阵问题——有多少人能得到他们想要的颜色？

Question

给定如下的位数组：

                      
         C0      C1      C2      C3     C4      C5
      **********************************************
   P0 *  0       0       1       0       1       0 *
   P1 *  0       1       0       0       1       0 *
   P2 *  0       0       0       1       1       0 *
   P3 *  1       0       0       0       0       1 *
   P4 *  0       0       0       0       0       0 *
   P5 *  0       0       0       0       0       0 *
   P6 *  1       0       0       0       0       0 *
      **********************************************

每一行代表不同的人 P_i，而每一列代表不同的颜色 C_j。如果给定的单元格 A[i][j] 为 1，则表示人 i 想要颜色 j。一个人只能得到一种颜色，一种颜色也只能给一个人。

总的来说，人数P>0，颜色数C>=0。

我怎样才能省时地计算出可以得到他们想要的颜色的最大人数？

上面例子的正确答案是 5。

人6（P6）只有一个愿望，所以他得到颜色0（C0）
既然C0被拿走了，P3只剩下一个愿望了，所以他得到了C5。
P0 得到 C2，P1 得到 C1，P2 得到 C3。

我的第一个想法是一个贪心算法，它只偏爱所需颜色最少的人（即行）。这在大多数情况下都有效，但对我来说太慢了，因为它在 O(P*(P*C)) 时间内运行，当 n = P = C 时等于 O(n^3)。任何关于可以更快解决问题的算法（或其他数据结构）的想法？

这可能与另一个类似问题重复，但我无法找到问题类型的正确名称，如果是这种情况，请多多包涵。

Answer 1

这是一个经典问题，称为最大基数二分匹配。在这里，您有一个二部图，其中一侧有对应于人的顶点，另一侧有对应于颜色的顶点。如果矩阵中相应的条目中有一个，则存在人和颜色之间的边。

在一般情况下，最著名的算法在最坏情况下的性能为 O(E*sqrt(V))，其中 E 是图中的边数，V 是顶点数。一种这样的算法称为 Hopcroft-Karp。我建议您阅读我链接的维基百科解释。

二维矩阵问题——有多少人能得到他们想要的颜色？

2D Matrix Problem - how many people can get a color that they want?

algorithm

data-structures