核心概述
适用于二分图与一般图的带权匹配求解，侧重 O(N^3) 级别的匈牙利与带权开花实现，用于获得最小/最大权（含完美匹配）解。
Description: Minimum/maximum weight matching. For bipartite graphs, use Hungarian/assignment in O(N^3). For general graphs, use Edmonds’ blossom algorithm for (minimum) weight perfect matching in O(N^3). Time: O(N^3) typical Status: tested
-
模型与目标
- 输入：无向图 G=(V,E)，边权 w(e) 可为正/负。
- 输出：匹配 M⊆E 最大化 Σ w(e)（或最小化，总是可通过取反统一）。
- 特例：完美匹配要求覆盖所有顶点（|V| 偶且可行）。
-
二分图带权匹配（匈牙利/指派）
- 适用：二分图，常以 N×N 成本矩阵表示。
- 思路：维护行/列势（dual labels），不断寻找 0 边上的增广路，必要时调整势以暴露新 0 边。
- 接口（据实现）：hungarian(cost) → 最小总成本与匹配对；最大权转换为最小成本可取 cost = C − w。
- 复杂度：O(N^3)。
-
一般图带权匹配（带权开花）
- 适用：一般无向图（含奇环），典型为“最小权完美匹配”；最大权同理取负权。
- 思路：在交替路/交替树框架下引入“开花（奇环）收缩”，配合对偶变量与允许边（tight edges）维护最优性条件（KKT/互补松弛），反复寻找允许的增广路或调整对偶以生成新允许边。
- 接口（据实现）：addEdge(u,v,w)，solve() → {val, mate[]}，val 为最优匹配权值，mate[i] 为匹配点或 -1。
- 复杂度：O(N^3)；实现复杂度高于匈牙利。
-
费用流方案（替代路径）
- 可将带权匹配转化为网络流最小费用最大流（073-图论-最小费用最大流），适合额外约束或非完全二分结构。
- 复杂度依赖费用流实现，通常 O(F E log V)。
-
输出语义
- 返回最优匹配权值与匹配对（从 mate 数组重建 {(i, mate[i]) | i < mate[i]}）。
- 最大/最小权的切换：取 w’ = −w 即可。
-
使用与注意
- 二分图优先使用匈牙利（简洁稳定）；一般图需带权开花（实现繁琐、但更通用）。
- 对负权边：可整体平移权值不改变最优解结构（注意数值范围）。
- 若只需“无权”最大匹配，请参见063-图论-一般图匹配或067-图论-HopcroftKarp（二分图）。
-
复杂度
- 匈牙利与带权开花均为 O(N^3) 级别；位集/优化常数可改善实际表现。