Kuhn-Munkres算法（二分图最大权完美匹配）

题目描述
给定一个完全二分图，其中左右两侧顶点数量相等（均为n），以及一个权值矩阵w[i][j]，表示左侧顶点i与右侧顶点j之间的连接权值。目标是找到一个完美匹配（即每个顶点都恰好匹配一次），使得所有匹配边的权值之和最大（或最小）。这个问题称为二分图最大权完美匹配（也称指派问题）。

解题过程

1. 问题转化与核心思想

• 若求最小权完美匹配，可将所有权值取相反数转化为最大权问题，因此我们以最大权为例讲解。
• 核心思想是对偶变量（顶标）与相等子图：
  • 为每个左侧顶点u设定顶标labelU[u]，每个右侧顶点v设定顶标labelV[v]。
  • 初始时，labelU[u] = max(w[u][v])（u所在行的最大值），labelV[v] = 0。
  • 满足labelU[u] + labelV[v] >= w[u][v]的对偶约束。
  • 相等子图：由满足labelU[u] + labelV[v] == w[u][v]的边构成的子图。
• 定理：若相等子图中存在完美匹配，则该匹配即为原图的最大权完美匹配。
• 算法步骤：在满足对偶约束的前提下，通过调整顶标，不断扩展相等子图，直到找到完美匹配。

2. 算法步骤详解
设左侧顶点集为U，右侧顶点集为V，大小均为n。

• 初始化：

  for u in range(n):
      labelU[u] = max(w[u][v] for v in range(n))
  for v in range(n):
      labelV[v] = 0
  matchingV = [-1] * n  # 记录右侧顶点v匹配的左侧顶点，-1表示未匹配
  

• 为每个左侧顶点u寻找匹配，使用DFS或BFS在相等子图中寻找增广路径。但Kuhn-Munkres采用匈牙利树方法，效率更高。
• 对每个左侧顶点u，执行以下步骤直到其匹配成功：
  a. 定义集合S（已访问的左侧顶点）、T（已访问的右侧顶点），初始S = {u}，T = {}。
  b. 在相等子图中，从S出发寻找增广路径：
  • 检查S到V\T的边（满足labelU[s] + labelV[v] == w[s][v]），若v未匹配，则找到增广路径，更新匹配并结束。
  • 若v已匹配，将v加入T，并将v的匹配点s'加入S，继续搜索。
    c. 若未找到增广路径，则需要调整顶标以扩展相等子图：
  • 计算调整量delta = min{labelU[s] + labelV[v] - w[s][v] | s in S, v not in T}。
  • 对所有s in S，执行labelU[s] -= delta。
  • 对所有v in T，执行labelV[v] += delta。
  • 调整后，至少有一条新边加入相等子图（满足labelU[s] + labelV[v] == w[s][v]），且保持对偶约束。
    d. 重复步骤b~c，直到当前顶点u匹配成功。
• 最终matchingV记录了最大权完美匹配方案，权重和为sum(labelU) + sum(labelV)。

3. 举例说明
假设n=3，权矩阵为：

w = [[3, 5, 1],
     [2, 4, 6],
     [7, 2, 3]]

• 初始化labelU = [5, 6, 7]（每行最大值），labelV = [0, 0, 0]。
• 处理u=0：相等子图包含边(0,1)（5+0=5）。匹配0-1。
• 处理u=1：相等子图中，从S={1}出发，边(1,2)满足6+0=6，v=2未匹配，匹配1-2。
• 处理u=2：相等子图中，从S={2}出发，无边满足相等条件。调整顶标：
  S={2}, T={}，计算delta = min(7+0-7, 7+0-2, 7+0-3) = 0？注意v not in T，但T为空，所以v可取0,1,2。实际上初始相等子图无边，应计算所有v：
  delta = min(7-7, 7-2, 7-3) = 0，但delta=0不会扩展新边。这里需注意：初始时labelU[2]=7，与w[2][0]=7相等，所以(2,0)应在相等子图中。因此步骤b中会先检查该边，若v=0已匹配（给u=1？不，匹配是matchingV记录右侧匹配，此时matchingV[0]=-1，所以v=0未匹配），可匹配2-0。
  实际执行中，算法会正确处理。调整顶标通常发生在S和T集合扩展后无法增广时。完整流程从略，最终匹配可能是0-1, 1-2, 2-0，权重和=5+6+7=18。

4. 复杂度与注意事项

• 时间复杂度：O(n³)，常见实现为O(n⁴)，但通过松弛操作可优化至O(n³)。
• 必须保证存在完美匹配（通常题目给定完全二分图）。
• 若求最小权，可将权值取负，或初始化labelU[u] = max(w[u][v])改为min，调整delta计算方式。

5. 关键理解点

• 顶标labelU和labelV是对偶问题的变量，调整顶标即在不破坏最优性的前提下扩大相等子图。
• 每次调整至少加入一条新边，保证算法在有限步收敛。
• 该算法是匈牙利算法的加权扩展，体现了线性规划对偶思想在图论中的应用。