一般图最大权匹配：带权带花树算法的线性规划框架与 C++ 实现

一般图最大权匹配：带权带花树算法的线性规划框架与 C++ 实现

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

本页主题是 OI-wiki 图匹配专题中的一般图最大权匹配：以「花（Blossom）」为核心的 Edmonds 带花树算法，如何从线性规划与原始对偶（Primal-Dual）的角度被推广到加权一般图，形成可在 $O(|V|^3)$ 时间内求解最大权完美匹配与最大权匹配的完整算法。读完本文，你将理解顶标（vertex labeling）、等边、互补松弛条件在算法中的角色，掌握缩花/拆花的实现原理，并能直接复用文中给出的 C++ 参考实现。

从二分图到一般图：奇环带来的核心困难

图匹配专题在 图匹配综述 中已经定义了匹配、最大匹配、最大权匹配与完美匹配等基础概念。二分图的匹配等价于网络流问题，性质良好；而一般图匹配与二分图匹配本质的区别在于：一般图可能存在奇环（奇数长度的环）。偶环可以视为二分图处理，但奇环会破坏增广路反转操作的正确性——沿奇环取反匹配边与非匹配边，会导致某些点出现在两条匹配边上，正如 一般图最大匹配 中所述。

带花树算法（Blossom Algorithm，由 Jack Edmonds 于 1961 年提出）的处理方式是：遇到奇环就把它缩成一个「花（Blossom）」，并把花中所有的点设为偶点。既然花上的点都可以成为偶点，就可以把整个花直接缩成一个偶点。注意，一个花可以包含其它花（即花是嵌套的）。该算法是第一个给出证明、说明最大匹配具有多项式复杂度的算法，经过一些修改后也可以解决一般图最大权匹配问题。

对于加权情形，这一问题同样可以写成线性规划并通过对偶理论求解，但需要对「花」进行一些特殊处理。

预备知识：顶标与等边

定义 $z_u$ 是点 $u$ 的顶标（vertex labeling），与二分图 KM 算法中定义的顶标含义相同（参见 二分图最大权匹配）。定义边 $e(u,v)$ 为「等边」（Equality Edge）当且仅当点 $u$ 和点 $v$ 的标号和等于边 $e$ 的权值：

$$ z_u + z_v = w(e) $$

此时边的标号 $z_e = z_u + z_v - w(e) = 0$。等边是构建交错树、寻找增广路的基础：算法只允许用等边进行增广，从而保证最终匹配中所有匹配边都是等边，进而保证匹配的最优性。

一般图最大权完美匹配的线性规划

原问题与对偶问题

由于一朵花最少有三个点，缩花后成为一个点。设 $O$ 为大小为 $\ge 3$ 奇数的集合的集合（包含所有花），$\gamma(S)$ 表示 $S$ 集合中的边：

$$ \begin{aligned} & \text{设} S\subseteq V \ & \gamma(S)={(u,v)\in E:u\in S,v\in S} \ & O={B\subseteq V:|B|\text{是奇数且}|B|\geq3} \ \end{aligned} $$

原问题（最大权完美匹配）为：

$$ \begin{aligned} & \max\sum_{e\in E}w(e)x_e \ & \text{限制：} \ & x(\delta(u))=1:\forall u\in V \ & x(\gamma(B))\leq\lfloor\frac{|B|}{2}\rfloor:\forall B\in O \ & x_e\geq0:\forall e\in E \ \end{aligned} $$

其中 $x(\delta(u))=1$ 表示每个点恰好连出一条匹配边；$x(\gamma(B))\leq\lfloor\frac{|B|}{2}\rfloor$ 表示一朵花内部至多选取一半数量的边（这是比二分图多出的约束，正是奇环带来的复杂性）。

通过原始对偶（Primal-Dual）方法，将其转换为对偶问题：

$$ \begin{aligned} & \min\sum_{u\in V}z_u+\sum_{B\in O}\left\lfloor\frac{|B|}{2}\right\rfloor z_B \ & \text{限制：} \ & z_B\geq0:\forall B\in O \ & z_e\geq0:\forall e\in E \ & \text{设} e=(u,v)，\text{这里} \ & \begin{array}{lll} z_e & = & z_u + z_v - w(e) + \sum_{\substack{B \in O \ u,v \in \gamma(B)}} z_B \end{array} \end{aligned} $$

注意对偶问题中 $z_e$ 的定义相比二分图多出了对 $z_B$ 的求和：即一条边 $e=(u,v)$ 若同时落在某些花 $B$ 的内部，还要累加这些花对应的对偶变量 $z_B$。

互补松弛条件与 $z_B$ 的含义

$x_e=1$ 的边是匹配边，$x_e=0$ 的边是非匹配边。和二分图一样，必须满足 $x_e\in{0,1}:\forall e\in E$，因此必须在最大权完美匹配时，让所有匹配边都是等边的（即 $z_e=0$）。

和二分图不同的是，一般图多了 $z_B$ 需要处理。下面考虑 $z_B$ 什么时候大于 $0$。

可以看出，尽量使 $z_B=0$ 是最好的做法，但在不得已时还是要让 $z_B>0$。在 $x(\gamma(B)) = \left\lfloor \dfrac{|B|}2 \right\rfloor \text{且} x(\delta(B)) = 1$ 时，让 $z_B>0$ 即可——因为除了这种情况，$z_B>0$ 是无意义的。

根据互补松弛条件（Complementary Slackness），有以下的对应关系：

• 对于选中的边 $e$，必有 $z_e=0$：

$$ x_e>0 \longrightarrow z_e=0,\quad \forall e\in E $$

• 对于选中的集合 $B$，$z_B>0 \longrightarrow x(\gamma(B))= \left\lfloor \dfrac{|B|}2 \right\rfloor$，即所有 $z_B>0$ 的集合 $B$，都被选了集合大小一半的边，也即集合 $B$ 是一朵花，选中花中的一条边进行增广。同时加入一个条件：$x(\delta(B))=1$，即只有花 $B$ 向外连了一条边的时候，$z_B>0$ 才是有意义的：

$$ z_B>0 \longrightarrow x(\gamma(B))=\left\lfloor\frac{|B|}2\right\rfloor, x(\delta(B))=1\quad \forall B\in O $$

以「等边」的概念结合带花树算法：用「等边」构成的增广路不断进行扩充，由于用来扩充的边全是「等边」，最后得到的最大权完美匹配仍然全是「等边」。

处理花的问题

当遇到花的时候，要将它缩成一个偶点，将花中所有点都设为偶点，并让它的 $z_B=0$。

由于缩花后会把花保存起来，直到满足某些条件才会拆开，所以不能用之前（无权带花树中）的方法记录花。如果没有特殊说明，之前提到的点，都包含缩花形成的偶点。

由于花也有可能缩成点被加入队列中，并且花的数量是不固定的，因此不能像之前一样枚举每个点来检查是否有增广路。因此，在进行 BFS 时，必须将所有未匹配的点都放入队列中。这样会同时产生很多棵交错树。

算法的四个步骤

整个算法可以分成四个步骤：

1. GROW（等边）：用「等边」构成交错树。
2. AUGMENT（增广）：找出增广路并扩充匹配。
3. SHRINK（缩花）：把花缩成一个点。
4. EXPAND（展开）：把花拆开。

在 AUGMENT 阶段，因为所有未匹配点都会在不同的交错树上，所以当增广时两棵交错树的偶点连在一起，就表示找到了一条增广路。

找不到等边扩充：调整 vertex labeling

和二分图一样，也会有找不到「等边」扩充的问题，这时就需要调整 vertex labeling。

vertex labeling 仍要维持大于等于的性质（可行性），而且既有的「等边」不能被改变，还要让 $z_B$ 尽量的小。为了描述调整规则，先定义奇偶点符号：

• 以 $u^−$ 来表示 $u$ 在交错树上为奇点。
• 以 $u^+$ 来表示 $u$ 在交错树上为偶点。
• 以 $u^\varnothing$ 来表示 $u$ 不在任何一棵交错树上。
• 之后所有提到的 $B$ 预设都是花，并同时代表缩花之后的点；花也可以有奇花偶花之分，因此也适用 $B^+$、$B^−$、$B^\varnothing$ 等符号。

设目前有 $r$ 棵交错树 $T_i=(U_{t_i},V_{t_i}):1\leq i\leq r$，令：

$$ \begin{aligned} d1 &= \min({z_e : e = (u^+,v^\varnothing)}) \ d2 &= \min({z_e : e = (u^+,v^+), ~ u^+ \in T_i, ~ v^+ \in T_j, ~ i \neq j}) / 2 \ d3 &= \min({z_{B^-} : B^- \in O}) / 2 \end{aligned} $$

注意这里 $B$ 是缩花之后的点，所以可以有奇偶性。设 $d=\min(d1,d2,d3)$，让：

$$ \begin{aligned} z_{u^+} - &= d \ z_{v^-} + &= d \ z_{B^+} + &= 2d \ z_{B^-} - &= 2d \ \end{aligned} $$

如果出现 $z_B=0(d=d3)$，为了防止 $z_B<0$ 的情况，就要把这朵花拆开（EXPAND）。拆花后只留下花里的交替路径，并把花里不在交替路径上的点设为未走访（$\varnothing$）。

如此便制造了一条（以上）的等边，既有等边保持不动，并维持了 $z_e\geq0:\forall e\in E$ 的性质，且最低限度增加了 $z_B$，可以继续找增广路了。

一般图最大权匹配：从完美匹配到最大匹配

以上求的是最大权完美匹配。求最大权匹配需要在 vertex labeling 额外增加一个限制：对于所有匹配点 $u$，$z_u>0$。

开始时先设所有的 $z_u=max({w(e):e\in E})/2$。vertex labeling 为 $0$ 的点最后将成为未匹配点——这正是「最大权匹配可以通过增加零边变成最大权完美匹配」这一思路在算法层面的体现：权重为 0 的匹配边没有收益，因此顶标恰好降到 0 的点不会被匹配。

参考实现：数据结构与核心函数

这里为了方便实现，使用边权乘 $2$来计算 $z_e$ 的值，这样就不会出现浮点数误差了。

存储结构

constexpr int INF = INT_MAX; constexpr int MAXN = 400; struct edge { int u, v, w; // 表示(u,v)为一条边其权重为w edge() {} edge(int u, int v, int w) : u(u), v(v), w(w) {} }; int n, n_x; // 有n个点，编号为 1 ~ n // n_x表示当前点加上花的数量，编号从n+1到n_x为花的节点 edge g[MAXN * 2 + 1][MAXN * 2 + 1]; // 图用邻接矩阵存储，因为最多有n-1朵花，所以大小为MAXN*2 vector<int> flower[MAXN * 2 + 1]; // flower[b]记录了花b中有哪些点 // 我们记录花中的点的方式是只记录花里面的最外层花

其中flower[b]只记录花里面最外层的元素（普通点或直接包含的子花），从而支持嵌套花的表示。

嵌套花的存储方式

下面是一个嵌套花的例子：

其中 ${ 6, 5, 8} \in b1,{ b1, 4, 3, 2, 11, 10, 9} \in b2$，存储为：

flower[b2] = {b1, 4, 3, 2, 11, 10, 9} flower[b1] = {6, 5, 8}

当花发生旋转后（如get_pr反转），存储变为：

flower[b2] = {9, b1, 4, 3, 2, 11, 10} flower[b1] = {5, 8, 6}

顶标、匹配、slack 与所属花

int lab[MAXN * 2 + 1]; // lab[u]用来记录z_u, lab[b]用来记录z_B int match[MAXN * 2 + 1], slack[MAXN * 2 + 1], st[MAXN * 2 + 1], pa[MAXN * 2 + 1]; // match[x]=y表示(x,y)是匹配，这里x、y可能是花 // slack[x]=u表示z(x,u)是所有和x相邻的边中最小的那条边 // 表示节点 x 所在的花是 b．如果 x=b 且 b<=n，则表示 x // 是一个普通节点（不属于任何花） 表示在交错树中，节点 v 的父节点是 u int flower_from[MAXN * 2 + 1][MAXN + 1], S[MAXN * 2 + 1], vis[MAXN * 2 + 1]; /* flower_from[b][x]=xs表示最大的包含x的b的子花是xs x是b里面的一个点，xs是b里面的一朵花或一个点，同时x=xs或x是xs的其中一个点 */ // S[u]={-1:没走过 0:偶点 1:奇点} // vis只用在找lca的时候检查是不是走过了 queue<int> q; // BFS找增广路用的queue

flower_from用于在缩花后快速定位某个原图点位于哪朵子花内，其含义可用下图说明：

flower_from[b2][6] = b1 flower_from[b2][5] = b1 flower_from[b2][9] = 9 flower_from[b1][6] = 6 以此类推

等边判定与 slack 维护

int e_delta(const edge &e) { // 计算ze，为了方便起见先把所有边的权重乘二 // 在花里面直接计算 e_delta 值会导致错误 return lab[e.u] + lab[e.v] - g[e.u][e.v].w * 2; } void update_slack(int u, int x) { // 以u更新slack[x]的值 if (!slack[x] || e_delta(g[u][x]) < e_delta(g[slack[x]][x])) { slack[x] = u; } } void set_slack(int x) { // 算出slack[x]的值，slack[x]=0表示x是交错树中的节点 slack[x] = 0; for (int u = 1; u <= n; ++u) { if (g[u][x].w > 0 && st[u] != x && S[st[u]] == 0) { update_slack(u, x); } } }

e_delta返回的就是边的标号 $z_e$（由于权重乘了 2，实现中用lab[e.u] + lab[e.v] - g[e.u][e.v].w * 2）。slack[x]记录与 $x$ 相邻的边中 $z_e$ 最小的那条边的另一个端点，这是顶标调整（计算 $d1,d2$）的关键辅助信息。

BFS 队列与所属花的传播

void q_push(int x) { // 把x丟到queue里面，我们设定queue不能直接push一朵花 if (x <= n) q.push(x); else { // 若要push花必须将花里面原图的点都添加到queue中 for (size_t i = 0; i < flower[x].size(); i++) { q_push(flower[x][i]); } } } void set_st(int x, int b) { // 将x所在的花设为b st[x] = b; if (x > n) { // 若x也是花的话，就必须要把x里面的点其所在的花也设为b for (size_t i = 0; i < flower[x].size(); ++i) { set_st(flower[x][i], b); } } }

q_push保证队列中只出现原图上的点（花被递归展开）；set_st则递归地把一朵花内所有元素（包括子花内的点）的st统一设置为新花编号，相当于带权版本中的「并查集缩点」。

花内交替路径定位：get_pr

int get_pr(int b, int xr) { // xr是flower[b]中的一个点，返回值pr是它的位置 // 为了方便程序运行，我们让 flower[b][0]~flower[b][pr]为花里的交替路 int pr = find(flower[b].begin(), flower[b].end(), xr) - flower[b].begin(); if (pr % 2 == 1) { // 检查他在花里的位置，如果 flower[b][0]~flower[b][pr] 不是交替路 // 就把整朵花反转，重新计算 pr // 让 flower[b][0]~flower[b][pr] 为花里的交替路 reverse(flower[b].begin() + 1, flower[b].end()); return (int)flower[b].size() - pr; } else return pr; }

例如：

• 使用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。

该函数保证flower[b][0] ~ flower[b][pr]构成花内的一段交替路径，为set_match与expand_blossom中的取反操作做好准备。

匹配边设置与增广

void set_match(int u, int v) { // 设置u和v为匹配边，u和v有可能是花 match[u] = g[u][v].v; if (u > n) { // 如果u是花的话 edge e = g[u][v]; int xr = flower_from[u][e.u]; // 找出e.u在flower[u]里的哪朵花上 int pr = get_pr(u, xr); // 找出xr的位置并让0~pr为花里的交替路径 for (int i = 0; i < pr; ++i) { // 把花里的交替路上的匹配边和非匹配边反转 set_match(flower[u][i], flower[u][i ^ 1]); } set_match(xr, v); // 设置(xr,v)为匹配边 rotate(flower[u].begin(), flower[u].begin() + pr, flower[u].end()); // 最后把pr设为花托，因为花的存法是flower[u][0]会是u的花托 // 所以要把flower[u][pr] rotate 到最前面 } } void augment(int u, int v) { // 把u和u的祖先全部增广，并设(u,v)为匹配边 for (;;) { int xnv = st[match[u]]; set_match(u, v); if (!xnv) return; set_match(xnv, st[pa[xnv]]); u = st[pa[xnv]]; v = xnv; } } int get_lca(int u, int v) { // 找出u,v在交错树上的lca static int t = 0; for (++t; u || v; swap(u, v)) { if (u == 0) continue; if (vis[u] == t) return u; vis[u] = t; // 这种方法可以不用清空vis数组 u = st[match[u]]; if (u) u = st[pa[u]]; } return 0; }

set_match在设置匹配边时若端点是花，需要先把花内交替路径上的匹配边/非匹配边取反（即对花内部做一次「增广」），再旋转花序列使花托位于首位，最后把花整体与外部点 $v$ 匹配。get_lca借助时间戳技巧在交错树上求 LCA，无需每次清空vis数组。

缩花：add_blossom

void add_blossom(int u, int lca, int v) { // 将u,v,lca这朵花缩成一个点 b // 交错树上u,v的lca即为花托 int b = n + 1; while (b <= n_x && st[b]) ++b; if (b > n_x) ++n_x; // 找出目前未使用的花的编号 lab[b] = 0; // 设置zB=0 S[b] = 0; // 整朵花为一个偶点 match[b] = match[lca]; // 设置花的匹配边为花托的匹配边 flower[b].clear(); flower[b].push_back(lca); for (int x = u, y; x != lca; x = st[pa[y]]) { flower[b].push_back(x); y = st[match[x]]; flower[b].push_back(y); q_push(y); } reverse(flower[b].begin() + 1, flower[b].end()); for (int x = v, y; x != lca; x = st[pa[y]]) { flower[b].push_back(x); y = st[match[x]]; flower[b].push_back(y); q_push(y); } // b中所有点以环形的方式加入flower[b]，并设花托为首个元素 set_st(b, b); // 把整朵花里所有的元素其所在的花设为b for (int x = 1; x <= n_x; ++x) { g[b][x].w = 0; g[x][b].w = 0; } for (int x = 1; x <= n; ++x) { flower_from[b][x] = 0; } for (size_t i = 0; i < flower[b].size(); ++i) { int xs = flower[b][i]; for (int x = 1; x <= n_x; ++x) { // 设置b和x相邻的边为b里面和x相邻的边e_delta最小的那条 if (g[b][x].w == 0 || e_delta(g[xs][x]) < e_delta(g[b][x])) { g[b][x] = g[xs][x]; g[x][b] = g[x][xs]; } } for (int x = 1; x <= n; ++x) { if (flower_from[xs][x]) { // 如果b里面的点xs有包含x // 那flower_from[b][x]就会是xs flower_from[b][x] = xs; } } } set_slack(b); // 最后必须要设置b的slack值 }

缩花操作的关键细节：

• 新花的编号取第一个未被使用的 $b$；
• 新花作为偶点，$z_B=0$，且继承花托 $lca$ 的匹配边；
• 花内点以环形顺序写入flower[b]（花托为首元素），路径上的偶点全部入队等待继续 BFS；
• 新花与外部点 $x$ 之间的边权，取花内所有点与 $x$ 相连边中 $e_delta$ 最小的那条，这与对偶问题中 $z_e$ 的更新保持一致；
• 最后用set_slack(b)初始化新花的 slack。

拆花：expand_blossom

void expand_blossom(int b) { // b是奇花且zB=0时，必须要把b拆开 // 因为只拆开b而已，所以如果b里面有包含其他的花 // 不需要把他们拆开 for (size_t i = 0; i < flower[b].size(); ++i) { set_st(flower[b][i], flower[b][i]); // 先把flower[b]里每个元素所在的花设为自己 } int xr = flower_from[b][g[b][pa[b]].u]; // xr表示交错路上b的父母节点在flower[b]里的哪朵花上 int pr = get_pr(b, xr); // 找出xr的位置并让0~pr为花里的交替路径 for (int i = 0; i < pr; i += 2) { // 把交替路径拆开到交错树中 // 并把交替路中的偶点丢到queue里 int xs = flower[b][i]; int xns = flower[b][i + 1]; pa[xs] = g[xns][xs].u; S[xs] = 1; S[xns] = 0; slack[xs] = 0; set_slack(xns); q_push(xns); } S[xr] = 1; // 这时xr会是奇点或奇花 pa[xr] = pa[b]; for (size_t i = pr + 1; i < flower[b].size(); ++i) { // 把花中所有不再交替路径上的点设为未走访 int xs = flower[b][i]; S[xs] = -1; set_slack(xs); } st[b] = 0; }

拆花只发生在奇花且 $z_B=0$时（即顶标调整中 $d=d3$ 的情况），否则会让 $z_B<0$ 破坏可行性。拆花时只拆开 $b$ 本身，若 $b$ 内部还嵌套着其他花则无需拆开。交替路径上的点被重新放回交错树并继续 BFS，不在交替路径上的点被标记为未走访（$S=-1$）。

等边的处理与增广判定：on_found_edge

bool on_found_edge(const edge &e) { // BFS时找到一条等边e // 要对它进行以下的处理 // 这里u一定是偶点 int u = st[e.u], v = st[e.v]; if (S[v] == -1) { // v是未走访节点 pa[v] = e.u; S[v] = 1; int nu = st[match[v]]; slack[v] = 0; slack[nu] = 0; S[nu] = 0; q_push(nu); } else if (S[v] == 0) { // v是偶点 int lca = get_lca(u, v); if (!lca) { // lca=0表示u,v在不同的交错树上，有增广路 augment(u, v); augment(v, u); return true; // 找到增广路 } else add_blossom(u, lca, v); // 否则u,v在同棵树上就会是一朵花，要缩花 } return false; }

BFS 扩展时遇到一条等边，按另一端点 $v$ 的状态分三类处理：

• $v$ 是未走访节点：将其设为奇点，把它的配偶作为偶点入队（GROW）；
• $v$ 是偶点且与 $u$ 不在同一交错树：get_lca返回 0，说明找到了增广路，执行 AUGMENT；
• $v$ 是偶点且与 $u$ 在同一棵交错树：u,v,lca构成一朵奇花，执行 SHRINK（缩花）。

主循环：matching

bool matching() { memset(S + 1, -1, sizeof(int) * n_x); memset(slack + 1, 0, sizeof(int) * n_x); q = queue<int>(); // 把queue清空 for (int x = 1; x <= n_x; ++x) { if (st[x] == x && !match[x]) { // 把所有非匹配点加入queue里面，并设为偶点 pa[x] = 0; S[x] = 0; q_push(x); } } if (q.empty()) return false; // 所有点都有匹配了 for (;;) { while (q.size()) { // BFS int u = q.front(); q.pop(); if (S[st[u]] == 1) continue; for (int v = 1; v <= n; ++v) { if (g[u][v].w > 0 && st[u] != st[v]) { if (e_delta(g[u][v]) == 0) { if (on_found_edge(g[u][v])) return true; } else update_slack(u, st[v]); } } } // 修改lab值 int d = INF; for (int u = 1; u <= n; ++u) { // 这是为了防止出现lab<0的情况发生 // 只要有任何一个lab[u]=0就结束程序 if (S[st[u]] == 0) d = min(d, lab[u]); } for (int b = n + 1; b <= n_x; ++b) { if (st[b] == b && S[b] == 1) d = min(d, lab[b] / 2); } for (int x = 1; x <= n_x; ++x) if (st[x] == x && slack[x]) { if (S[x] == -1) d = min(d, e_delta(g[slack[x]][x])); else if (S[x] == 0) d = min(d, e_delta(g[slack[x]][x]) / 2); } for (int u = 1; u <= n; ++u) { if (S[st[u]] == 0) { if (lab[u] == d) return false; // 如果lab[u]=0就直接结束程序 lab[u] -= d; } else if (S[st[u]] == 1) lab[u] += d; } for (int b = n + 1; b <= n_x; ++b) { if (st[b] == b) { if (S[st[b]] == 0) lab[b] += d * 2; else if (S[st[b]] == 1) lab[b] -= d * 2; } } q = queue<int>(); // 把queue清空 for (int x = 1; x <= n_x; ++x) { // 检查看看有没有增广路径产生 if (st[x] == x && slack[x] && st[slack[x]] != x && e_delta(g[slack[x]][x]) == 0) if (on_found_edge(g[slack[x]][x])) return true; } for (int b = n + 1; b <= n_x; ++b) { // EXPAND的操作，把所有lab[b]=0的奇花拆开 if (st[b] == b && S[b] == 1 && lab[b] == 0) expand_blossom(b); } } return false; }

一次matching()的流程对应前文的四步骤：

1. 所有未匹配点入队并设为偶点（多棵交错树同时生长）；
2. BFS 沿等边扩展（GROW），遇到增广路立即 AUGMENT 并返回true；
3. BFS 无路可走时计算 $d=\min(d1,d2,d3)$（对应公式中的 $d1,d2,d3$），按奇偶点规则更新 $lab$，其中偶点 $-d$、奇点 $+d$、偶花 $+2d$、奇花 $-2d$；
4. 若 $lab[u]=0$（某偶点的顶标降为 0）则返回false，表示已达到最大权匹配；否则检查 slack 中是否有新等边产生增广路，并 EXPAND 所有 $lab[b]=0$ 的奇花，然后清空队列重新开始下一轮 BFS。

注意实现中 $d$ 的计算与顶标更新完全对应前面理论部分的 $d1,d2,d3$ 与 $z_{u^+}-=d,\ z_{v^-}+=d,\ z_{B^+}+=2d,\ z_{B^-}-=2d$ 规则。

主函数与初始化

pair<long long, int> weight_blossom() { // 主函数，一开始先初始化 memset(match + 1, 0, sizeof(int) * n); n_x = n; // 一开始没有花 int n_matches = 0; long long tot_weight = 0; for (int u = 0; u <= n; ++u) { // 先把自己所在的花设为自己 st[u] = u; flower[u].clear(); } int w_max = 0; for (int u = 1; u <= n; ++u) for (int v = 1; v <= n; ++v) { // u是一个点时，里面所包含的点只有自己 flower_from[u][v] = (u == v ? u : 0); w_max = max(w_max, g[u][v].w); // 找出最大的边权 } for (int u = 1; u <= n; ++u) lab[u] = w_max; // 让所有的lab=最大的边权 // 因为这里实现是用边权乘二来计算ze的值所以不用除以二 while (matching()) ++n_matches; for (int u = 1; u <= n; ++u) if (match[u] && match[u] < u) tot_weight += g[u][match[u]].w; return make_pair(tot_weight, n_matches); }

初始化时把每个点的顶标设为最大边权（因为边权乘 2，所以顶标直接取 $w_{max}$ 而无需再除以 2），与理论部分「开始时先设所有的 $z_u=max({w(e):e\in E})/2$」相对应。算法反复调用matching()直至无法增广，最后统计匹配边权总和与匹配边数。

使用前必须初始化邻接矩阵：

void init_weight_graph() { // 在把边输入到图里面前必须要初始化 // 因为是最大权匹配所以把不存在的边设为0 for (int u = 1; u <= n; ++u) for (int v = 1; v <= n; ++v) g[u][v] = edge(u, v, 0); }

由于求的是最大权匹配，不存在的边权重设为 0，等效于「不匹配」，这与「最大权匹配可以通过增加零边变成最大权完美匹配」的思路一致。

复杂度分析

每朵花在一次 BFS 中只会被缩花或拆花一次。每次缩花或拆花的时间复杂度为 $O(|V|)$，最多总共有 $O(|V|)$ 朵花，所以花的处理花费 $O(|V|^2)$ 的时间。而 BFS 花费 $O(|V| + |E|)$ 的时间复杂度。因此，找增广路花费：

$$ O(|V| + |E|) + O(|V|^2) = O(|V|^2) $$

最多做 $|V|$ 次 BFS（每次matching()至少增加一条匹配边），所以总时间复杂度为：

$$ O(|V|^3) $$

与仓库中相关算法的关系

• 本页的等边、顶标概念继承自 二分图最大权匹配（KM 算法），但一般图多出对 $z_B$ 与缩花/拆花的处理；
• 无权版本的缩花思路参见 一般图最大匹配（带花树），其中general-match_1.cpp（源码）实现了基于 BFS 与orig/label数组的无权带花树；本页的加权版本在此基础上加入了lab、slack与嵌套花存储，因此 BFS 中必须将所有未匹配点入队、同时维护多棵交错树；
• 匹配、增广路、交错树等基础概念与 Berge 引理参见 图匹配综述。

习题

• UOJ #81. 一般图最大权匹配

参考资料

1. Kolmogorov, Vladimir (2009), "Blossom V: A new implementation of a minimum cost perfect matching algorithm"
2. 从匈牙利算法到带权带花树——详解对偶问题在图匹配上的应用

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki