一般图最大权匹配
本页从一般图最大权完美匹配到一般图最大权匹配（最大权匹配可以通过增加零边变成最大权完美匹配）．
预备知识
花（blossom）
一般图匹配和二分图匹配不同的是，图可能存在奇环．可以将偶环视为二分图．
带花树算法（Blossom Algorithm）的处理方式时是遇到奇环就把它缩成一个 花（Blossom） ，并把花中所有的点设为偶点．既然花上的点都可以成为偶点，那么可以把整个花直接缩成一个偶点．注意，一个花可以包含其它花．
这也可以变成线性规划和对偶问题，但是要对花进行一些处理．
顶标（vertex labeling）和等边（Equality Edge）
定义 𝑧𝑢zu
是点 𝑢u 的顶标（vertex labeling），与 𝐾𝑀KM 算法中定义的顶标含义相同．定义边 𝑒(𝑢,𝑣)e(u,v) 为 "等边" 当且仅当点 𝑢u 和点 𝑣v 的标号和等于边 𝑒e 的权值（𝑧𝑢 +𝑧𝑣 =𝑤(𝑒)zu+zv=w(e)），此时边的标号 𝑧𝑒 =𝑧𝑢 +𝑧𝑣 −𝑤(𝑒) =0ze=zu+zv−w(e)=0．
一般图最大权完美匹配的线性规划
定义
因为一朵花最少有三个点，缩花后成为一个点．设 𝑂O 为大小为 ≥3≥3 奇数的集合的集合（包含所有花），𝛾(𝑆)γ(S) 表示 𝑆S 集合中的边．
设𝑆⊆𝑉𝛾(𝑆)={(𝑢,𝑣)∈𝐸:𝑢∈𝑆,𝑣∈𝑆}𝑂={𝐵⊆𝑉:|𝐵|是奇数且|𝐵|≥3}设S⊆Vγ(S)={(u,v)∈E:u∈S,v∈S}O={B⊆V:|B|是奇数且|B|≥3}
对偶问题
原问题 max∑𝑒∈𝐸𝑤(𝑒)𝑥𝑒限制：𝑥(𝛿(𝑢))=1:∀𝑢∈𝑉𝑥(𝛾(𝐵))≤⌊|𝐵|2⌋:∀𝐵∈𝑂𝑥𝑒≥0:∀𝑒∈𝐸max∑e∈Ew(e)xe限制：x(δ(u))=1:∀u∈Vx(γ(B))≤⌊|B|2⌋:∀B∈Oxe≥0:∀e∈E
然后通过原始对偶（Primal-Dual）将问题转换为对偶问题．
对偶问题 min∑𝑢∈𝑉𝑧𝑢+∑𝐵∈𝑂⌊|𝐵|2⌋𝑧𝐵限制：𝑧𝐵≥0:∀𝐵∈𝑂𝑧𝑒≥0:∀𝑒∈𝐸设𝑒=(𝑢,𝑣)，这里𝑧𝑒=𝑧𝑢+𝑧𝑣−𝑤(𝑒)+∑𝐵∈𝑂𝑢,𝑣∈𝛾(𝐵)𝑧𝐵min∑u∈Vzu+∑B∈O⌊|B|2⌋zB限制：zB≥0:∀B∈Oze≥0:∀e∈E设e=(u,v)，这里ze=zu+zv−w(e)+∑B∈Ou,v∈γ(B)zB
𝑥𝑒 =1xe=1 的边是匹配边，𝑥𝑒 =0xe=0 的边是非匹配边．和二分图一样，我们必须满足 𝑥𝑒 ∈{0,1} :∀𝑒 ∈𝐸xe∈{0,1}:∀e∈E．因此必须在最大权完美匹配的时候，让所有匹配边都是 等边 的．
和二分图不同的是，一般图多了 𝑧𝐵zB 要处理．下面考虑 𝑧𝐵zB 什么时候大于 00．
可以看出，尽量使 𝑧𝐵 =0zB=0 是最好的做法，但在不得已时还是要让 𝑧𝐵 >0zB>0．在 𝑥(𝛾(𝐵)) =⌊|𝐵|2⌋且𝑥(𝛿(𝐵)) =1x(γ(B))=⌊|B|2⌋且x(δ(B))=1 时，让 𝑧𝐵 >0zB>0 即可．因为除了在这种情况下，𝑧𝐵 >0zB>0 是无意义的．
根据互补松弛条件，有以下的对应关系：
- 对于选中的边 𝑒e，必有 𝑧𝑒 =0ze=0．
𝑥𝑒>0⟶𝑧𝑒=0,∀𝑒∈𝐸xe>0⟶ze=0,∀e∈E
- 对于选中的集合 _B_ ，𝑧𝐵 >0 ⟶𝑥(𝛾(𝐵)) =⌊|𝐵|2⌋zB>0⟶x(γ(B))=⌊|B|2⌋，即所有 𝑧𝐵 >0zB>0 的集合 𝐵B，都被选了集合大小一半的边，也即集合 𝐵B 是一朵花，选中花中的一条边进行增广．同时，我们加入一个条件：𝑥(𝛿(𝐵)) =1x(δ(B))=1，即只有花 𝐵B 向外连了一条边的时候，𝑧𝐵 >0zB>0 才是有意义的．
𝑧𝐵>0⟶𝑥(𝛾(𝐵))=⌊|𝐵|2⌋,𝑥(𝛿(𝐵))=1∀𝐵∈𝑂zB>0⟶x(γ(B))=⌊|B|2⌋,x(δ(B))=1∀B∈O
以「等边 」的概念，结合之前的带花树算法：用「等边」构成的增广路不断进行扩充，由于用来扩充的边全是「等边」，最后得到的最大权完美匹配仍然全是「等边」．
处理花的问题
当遇到花的时候，要将它缩成一个偶点．将花中所有点都设为偶点，并让它的 𝑧𝐵 =0zB=0．
由于缩花后会把花保存起来，直到满足某些条件才会拆开，所以不能用之前的方法记录花．
如果没有特殊说明，之前提到的点，都包含缩花形成的偶点．
由于花也有可能缩成点被加入队列中，并且花的数量是不固定的，因此不能像之前一样枚举每个点来检查是否有增广路．因此，在进行广度优先搜索（BFS）时，必须将所有未匹配的点都放入队列中．
这样会同时产生很多棵交错树．
算法的四个步骤
这个算法可以分成四个步骤．
- GROW（等边）：用 "等边" 构成交错树．
- AUGMENT（增广）：找出增广路并扩充匹配．
- SHRINK（缩花）：把花缩成一个点．
- EXPAND（展开）：把花拆开．
在 AUGMENT 阶段时，因为所有未匹配点都会在不同的交错树上，所以当增广时两棵交错树的偶点连在一起，就表示找到了一条增广路．
找不到等边扩充
和二分图一样，也会有找不到「等边」扩充的问题．这时就需要调整 vertex labeling．
调整 VERTEX LABELING
vertex labeling 仍要维持大于等于的性质，而且既有的「等边」不能被改变，还要让 𝑧𝐵zB 尽量的小．
定义符号 奇偶点
以 𝑢−u− 来表示 𝑢u 在交错树上为奇点． 以 𝑢+u+ 来表示 𝑢u 在交错树上为偶点． 以 𝑢∅u∅ 来表示 𝑢u 不在任何一棵交错树上． 之后所有提到的 𝐵B 预设都是花，并同时代表缩花之后的点． 花也可以有奇花偶花之分，因此也适用 𝐵+B+、𝐵−B−、𝐵∅B∅ 等符号．
设目前有 r 棵交错树 𝑇𝑖 =(𝑈𝑡𝑖,𝑉𝑡𝑖) :1 ≤𝑖 ≤𝑟Ti=(Uti,Vti):1≤i≤r，令
𝑑1=min({𝑧𝑒:𝑒=(𝑢+,𝑣∅)})𝑑2=min({𝑧𝑒:𝑒=(𝑢+,𝑣+), 𝑢+∈𝑇𝑖, 𝑣+∈𝑇𝑗, 𝑖≠𝑗})/2𝑑3=min({𝑧𝐵−:𝐵−∈𝑂})/2d1=min({ze:e=(u+,v∅)})d2=min({ze:e=(u+,v+), u+∈Ti, v+∈Tj, i≠j})/2d3=min({zB−:B−∈O})/2
注意这里 _B_ 是缩花之后的点，所以可以有奇偶性．
设 𝑑 =𝑚𝑖𝑛(𝑑1,𝑑2,𝑑3)d=min(d1,d2,d3)，让
𝑧𝑢+−=𝑑𝑧𝑣−+=𝑑𝑧𝐵++=2𝑑𝑧𝐵−−=2𝑑zu+−=dzv−+=dzB++=2dzB−−=2d
如果出现 𝑧𝐵 =0(𝑑 =𝑑3)zB=0(d=d3)，为了防止 𝑧𝐵 <0zB<0 的情况，所以要把这朵花拆了 (EXPAND)． 拆花后只留下花里的交替路径，并把花里不在交替路径上的点设为未走访 (∅∅)．
如此便制造了一条（以上）的等边，既有等边保持不动，并维持了 𝑧𝑒 ≥0 :∀𝑒 ∈𝐸ze≥0:∀e∈E 的性质，且最低限度增加了 𝑧𝐵zB，可以继续找增广路了．
一般图最大权匹配
以上求的是最大权完美匹配，求最大权匹配需要在 vertex labeling 额外增加一个限制：对于所有匹配点 𝑢u，𝑧𝑢 >0zu>0．
开始时先设所有的 𝑧𝑢 =𝑚𝑎𝑥({𝑤(𝑒) :𝑒 ∈𝐸})/2zu=max({w(e):e∈E})/2．
vertex labeling 为 00 的点最后将成为未匹配点．
参考代码
这里为了方便实现，使用边权乘 22 来计算 𝑧𝑒ze 的值，这样就不会出现浮点数误差了．
存储
---|---
下面是嵌套花的例子．
其中 {6,5,8} ∈𝑏1,{𝑏1,4,3,2,11,10,9} ∈𝑏2{6,5,8}∈b1,{b1,4,3,2,11,10,9}∈b2．存储为：
---|---
---|---
---|---
---|---
---|---
---|---
---|---
如果使用 get_pr(b2,11)，flower[b2] 会变成 {9,10,11,2,3,4,b1}，并返回 2．
如果使用 get_pr(b2,2)，flower[b2] 会变成 {9,b1,4,3,2,11,10}，并返回 4．
---|---
增加一朵奇花
---|---
拆花
---|---
尝试增广一条等边
---|---
增广
---|---
主函数
---|---
初始化
很重要 使用前一定要初始化
---|---
## 复杂度分析
每朵花在一次 BFS 中只会被缩花或拆花一次．每次缩花或拆花的时间复杂度为 𝑂(|𝑉|)O(|V|)．最多总共有 𝑂(|𝑉|)O(|V|) 朵花，所以花的处理花费 𝑂(|𝑉|2)O(|V|2) 的时间．而 BFS 花费 𝑂(|𝑉| +|𝐸|)O(|V|+|E|) 的时间复杂度．因此，找增广路花费 𝑂(|𝑉| +|𝐸|) +𝑂(|𝑉|2) =𝑂(|𝑉|2)O(|V|+|E|)+O(|V|2)=O(|V|2) 的时间复杂度．
最多做 |𝑉||V| 次 BFS．所以，总时间复杂度为 𝑂(|𝑉|3)O(|V|3)．
## 习题
* [UOJ #81. 一般图最大权匹配](https://uoj.ac/problem/81)
## 参考资料
1. [Kolmogorov, Vladimir (2009), "Blossom V: A new implementation of a minimum cost perfect matching algorithm"](http://pub.ist.ac.at/~vnk/papers/BLOSSOM5.html)
2. [从匈牙利算法到带权带花树——详解对偶问题在图匹配上的应用](https://www.luogu.com.cn/blog/potassium/solution-p6699)
* * *
> __本页面最近更新： 2026/1/7 08:56:54，[更新历史](https://github.com/OI-wiki/OI-wiki/commits/master/docs/graph/graph-matching/general-weight-match.md)
> __发现错误？想一起完善？[在 GitHub 上编辑此页！](https://oi-wiki.org/edit-landing/?ref=/graph/graph-matching/general-weight-match.md "edit.link.title")
> __本页面贡献者：[Tiphereth-A](https://github.com/Tiphereth-A), [310552025atNYCU](https://github.com/310552025atNYCU), [Henry-ZHR](https://github.com/Henry-ZHR), [Xeonacid](https://github.com/Xeonacid), [yuhuoji](https://github.com/yuhuoji), [accelsao](https://github.com/accelsao), [c-forrest](https://github.com/c-forrest), [Enter-tainer](https://github.com/Enter-tainer)
> __本页面的全部内容在**[CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/deed.zh) 和 [SATA](https://github.com/zTrix/sata-license)** 协议之条款下提供，附加条款亦可能应用