一般图最大权匹配带权带花树算法的线性规划框架与 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_e1$ 的边是匹配边$x_e0$ 的边是非匹配边。和二分图一样必须满足 $x_e\in{0,1}:\forall e\in E$因此必须在最大权完美匹配时让所有匹配边都是等边的即 $z_e0$。和二分图不同的是一般图多了 $z_B$ 需要处理。下面考虑 $z_B$ 什么时候大于 $0$。可以看出尽量使 $z_B0$ 是最好的做法但在不得已时还是要让 $z_B0$。在 $x(\gamma(B)) \left\lfloor \dfrac{|B|}2 \right\rfloor \text{且} x(\delta(B)) 1$ 时让 $z_B0$ 即可——因为除了这种情况$z_B0$ 是无意义的。根据互补松弛条件Complementary Slackness有以下的对应关系对于选中的边 $e$必有 $z_e0$$$ x_e0 \longrightarrow z_e0,\quad \forall e\in E $$对于选中的集合 $B$$z_B0 \longrightarrow x(\gamma(B)) \left\lfloor \dfrac{|B|}2 \right\rfloor$即所有 $z_B0$ 的集合 $B$都被选了集合大小一半的边也即集合 $B$ 是一朵花选中花中的一条边进行增广。同时加入一个条件$x(\delta(B))1$即只有花 $B$ 向外连了一条边的时候$z_B0$ 才是有意义的$$ z_B0 \longrightarrow x(\gamma(B))\left\lfloor\frac{|B|}2\right\rfloor, x(\delta(B))1\quad \forall B\in O $$以「等边」的概念结合带花树算法用「等边」构成的增广路不断进行扩充由于用来扩充的边全是「等边」最后得到的最大权完美匹配仍然全是「等边」。处理花的问题当遇到花的时候要将它缩成一个偶点将花中所有点都设为偶点并让它的 $z_B0$。由于缩花后会把花保存起来直到满足某些条件才会拆开所以不能用之前无权带花树中的方法记录花。如果没有特殊说明之前提到的点都包含缩花形成的偶点。由于花也有可能缩成点被加入队列中并且花的数量是不固定的因此不能像之前一样枚举每个点来检查是否有增广路。因此在进行 BFS 时必须将所有未匹配的点都放入队列中。这样会同时产生很多棵交错树。算法的四个步骤整个算法可以分成四个步骤GROW等边用「等边」构成交错树。AUGMENT增广找出增广路并扩充匹配。SHRINK缩花把花缩成一个点。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_B0(dd3)$为了防止 $z_B0$ 的情况就要把这朵花拆开EXPAND。拆花后只留下花里的交替路径并把花里不在交替路径上的点设为未走访$\varnothing$。如此便制造了一条以上的等边既有等边保持不动并维持了 $z_e\geq0:\forall e\in E$ 的性质且最低限度增加了 $z_B$可以继续找增广路了。一般图最大权匹配从完美匹配到最大匹配以上求的是最大权完美匹配。求最大权匹配需要在 vertex labeling 额外增加一个限制对于所有匹配点 $u$$z_u0$。开始时先设所有的 $z_umax({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表示当前点加上花的数量编号从n1到n_x为花的节点 edge g[MAXN * 2 1][MAXN * 2 1]; // 图用邻接矩阵存储因为最多有n-1朵花所以大小为MAXN*2 vectorint 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如果 xb 且 bn则表示 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里面的一朵花或一个点同时xxs或x是xs的其中一个点 */ // S[u]{-1:没走过 0:偶点 1:奇点} // vis只用在找lca的时候检查是不是走过了 queueint q; // BFS找增广路用的queueflower_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_print 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_blossomvoid 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; // 设置zB0 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_B0$且继承花托 $lca$ 的匹配边花内点以环形顺序写入flower[b]花托为首元素路径上的偶点全部入队等待继续 BFS新花与外部点 $x$ 之间的边权取花内所有点与 $x$ 相连边中 $e_delta$ 最小的那条这与对偶问题中 $z_e$ 的更新保持一致最后用set_slack(b)初始化新花的 slack。拆花expand_blossomvoid expand_blossom(int b) { // b是奇花且zB0时必须要把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_B0$时即顶标调整中 $dd3$ 的情况否则会让 $z_B0$ 破坏可行性。拆花时只拆开 $b$ 本身若 $b$ 内部还嵌套着其他花则无需拆开。交替路径上的点被重新放回交错树并继续 BFS不在交替路径上的点被标记为未走访$S-1$。等边的处理与增广判定on_found_edgebool 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) { // lca0表示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缩花。主循环matchingbool matching() { memset(S 1, -1, sizeof(int) * n_x); memset(slack 1, 0, sizeof(int) * n_x); q queueint(); // 把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) { // 这是为了防止出现lab0的情况发生 // 只要有任何一个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 queueint(); // 把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()的流程对应前文的四步骤所有未匹配点入队并设为偶点多棵交错树同时生长BFS 沿等边扩展GROW遇到增广路立即 AUGMENT 并返回trueBFS 无路可走时计算 $d\min(d1,d2,d3)$对应公式中的 $d1,d2,d3$按奇偶点规则更新 $lab$其中偶点 $-d$、奇点 $d$、偶花 $2d$、奇花 $-2d$若 $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$ 规则。主函数与初始化pairlong 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_umax({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. 一般图最大权匹配参考资料Kolmogorov, Vladimir (2009), Blossom V: A new implementation of a minimum cost perfect matching algorithm从匈牙利算法到带权带花树——详解对偶问题在图匹配上的应用【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考