給定一個位陣列，如下所示：
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，則表示我想要顏色 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)。任何可以更快地解決問題的演算法（或其他資料結構）的想法？
這可能是另一個類似問題的重復，但我在找到問題型別的正確名稱時遇到了麻煩，如果是這種情況，請多多包涵。
uj5u.com熱心網友回復：
這是一個被稱為最大基數二分匹配的經典問題。在這里，您有一個二分圖，其中一側的頂點對應于人，另一側的頂點對應于顏色。如果矩陣的相應條目中有一條邊，則存在人和顏色之間的邊。
在一般情況下，最知名的演算法在最差情況下的性能為 O(E*sqrt(V))，其中 E 是圖中的邊數，V 是頂點數。一種這樣的演算法稱為Hopcroft-Karp。我建議您閱讀我鏈接的維基百科解釋。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/475518.html
下一篇：二叉堆能做什么而二叉搜索樹不能？