最大化全局幸福感的情侣配对问题（二分图最大权匹配求解）

哈哈，这个迟来的情人节技术题有点甜啊！其实这就是经典的二分图最大权匹配问题，刚好完美对应你说的男女配对求全局幸福最大化的场景，我给你捋捋思路和可行的解法：

你描述的场景完全符合二分图的定义：男性和女性是两个互不相交的顶点集合，每个男性和女性之间的幸福值就是连接两个顶点的边的权重。我们需要找到一组边，满足每个顶点最多被一条边覆盖（也就是每个人只配对一次），且这组边的总权重最大，同时边的数量要达到min(M, W)——毕竟要尽可能多的促成配对嘛。

针对这个问题，有几个成熟的解法可以直接用：

• KM算法（Kuhn-Munkres算法）：这是专门为完备二分图（也就是M=W的情况）设计的最大权匹配算法。如果M≠W也没关系，我们可以把少的那一方补全，给新增的“虚拟”配对设置幸福值为0，这样就能转化为完备二分图来处理了。它的核心逻辑是给每个顶点设置一个“顶标”，通过不断寻找增广路径来调整匹配关系，最终找到全局最优解，时间复杂度是O(n³)，n是两个集合中较大的那个数量。
• 变种匈牙利算法：标准的匈牙利算法是用来求最大匹配数的，但稍微修改一下就能处理最大权匹配。比如我们可以把幸福值转化为“代价”（比如用一个远大于最大幸福值的数减去原幸福值），把问题转化为最小权匹配，再用匈牙利算法求解，适合规模不大的场景。
• 网络流算法：我们可以把配对问题转化为最大费用最大流问题来解决，步骤大概是这样的：
  1. 新建一个源点，给每个男性节点连一条容量为1、费用为0的边；
  2. 每个男性节点和对应的女性节点连一条容量为1、费用为幸福值（或者取相反数，看你用的是最大费用还是最小费用流实现）的边；
  3. 每个女性节点再连一条到汇点的容量为1、费用为0的边；
  4. 求解从源点到汇点的最大费用最大流，最终流经过的男女节点连接边，就是最优的配对组合，流的大小刚好是min(M, W)。

比如假设我们有2名男性，2名女性，幸福矩阵是：

[[5, 3],
 [4, 6]]

最优配对就是男1配女1（幸福值5）、男2配女2（幸福值6），总幸福值11，这是全局最大的。如果是2名男性，3名女性，幸福矩阵是：

[[5, 3, 4],
 [4, 6, 2]]

最优配对还是男1配女1、男2配女2，总幸福值11，因为我们要优先选权重最大且不冲突的配对。

内容的提问来源于stack exchange，提问作者Peter