有些男性为 M1、M2、...Mn，有些女性则为 W1、W2、W3、.....Wm。并且还给出了一个二维矩阵，该矩阵讲述了他喜欢的男人的兴趣。 计算与所有男性和女性结婚所需的婚姻数量。
约束:一个男人可以与多个女人结婚，一个女人可以与多个男人结婚。
我认为的方法:我认为这个问题可以用二分法解决，但我很困惑用什么案例来开始这个问题。请指导解决这个问题。
最佳答案
您想要最小的边缘覆盖，这是一个多项式时间问题。您可以使用 Hopcroft–Karp 算法来查找最大匹配，然后从每个未连接点到其任何可能的配对绘制一条边。
关于algorithm - 最小结婚可能算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12200554/