2

有一些男性 M1, M2, .... Mn，一些女性被赋予 W1, W2, W3, .....Wm。并且还给出了一个二维矩阵，它讲述了他喜欢的男人的兴趣。计算与所有男人和女人结婚所需的婚姻数量。

constraint:一个男人可以和多个女人结婚，一个女人可以和多个男人结婚。

Approach that I think: 我认为这个问题可以用二分法解决，但我很困惑是什么情况下引发了这个问题。请指导解决这个问题。

4

1 回答 1

2

您想要最小的边缘覆盖，这是一个多项式时间问题。您可以使用 Hopcroft–Karp 算法找到最大匹配，然后从每个未连接的点到其任何可能的配对点绘制一条边。

见：http ://en.wikipedia.org/wiki/Edge_cover

于 2012-08-30T16:25:20.883 回答