企业官网建设流程全解析

一般图最大匹配完全指南：带花树算法与基于高斯消元的新方法（OI-wiki 实战解析）

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

一般图最大匹配（maximum cardinality matching）是图论与组合优化中的经典问题，与二分图匹配不同，一般图中可能存在的奇环使得直接套用增广路算法会失败。本文以 OI-wiki 的 docs/graph/graph-matching/general-match.md 为骨架，完整讲解由 Jack Edmonds 于 1961 年提出的带花树算法（Blossom Algorithm），以及另一条基于 Tutte 矩阵与高斯消元的代数路线，并结合仓库内的完整 C++ 实现与测试数据，帮助你从原理到代码彻底掌握两类一般图最大匹配算法，能够直接解决 UOJ #79 等经典问题。

为什么一般图匹配比二分图匹配更难

在深入算法之前，先回顾基本概念。设 $G=(V,E)$ 是无向图，边集 $M\subseteq E$ 若两两没有公共端点，则称 $M$ 为 $G$ 的一个匹配；大小为最大的匹配称为最大匹配。二分图中的匹配问题可以转化为网络流问题，性质良好，因此容易处理；而一般图（可能含奇环）的匹配则需要专门的算法。相关概念（交错路、增广路、交错树、Berge 引理、Tutte 定理）可先阅读 docs/graph/graph-matching/graph-match.md，它系统介绍了匹配问题的统一框架：反复寻找增广路并反转，直到不存在增广路，即得到最大匹配（Berge 引理）。

一般图匹配的困难之处在于奇环。如下图所示，若图存在奇环，直接对匹配边和非匹配边取反（即沿一条看似可行的路径做增广），会使取反后的 $M$ 不合法——某些点会同时出现在两条匹配边上，问题恰恰出在奇环上：

因此，处理一般图最大匹配的关键，就是找到一种方法来"消化"奇环带来的冲突，这正是带花树算法要解决的问题。

带花树算法（Blossom Algorithm）

开花算法（Blossom Algorithm，也被称为带花树）由 Jack Edmonds 在 1961 年提出，可解决一般图最大匹配问题，经过修改后也可解决一般图最大权匹配问题。它也是第一个证明最大匹配问题有多项式复杂度的算法。

从二分图增广到 o/i 标记

从二分图的角度出发，每次枚举一个未匹配点作为根，将其标记为「o」，然后沿边交错标记「o」与「i」。不难发现，「i」到「o」之间的边是匹配边。

假设当前点是 $v$，相邻点为 $u$，分为两种情况：

1. $u$ 未拜访过：若 $u$ 是未匹配点，则找到了增广路径；否则从 $u$ 的配偶继续找增广路（将其配偶标记为「o」并入队）。
2. $u$ 已拜访过：若遇到标记为「o」的点，说明遇到了奇环，需要缩花（shrink blossom）；否则遇到的是偶环，直接跳过。

遇到偶环时可以将其视为二分图情形处理，因此可以忽略；遇到奇环时则需要缩花，在缩花后的新图中继续找增广路：

缩花的正确性：两张图的增广路等价

设原图为 $G$，缩花后的图为 $G'$，只需证明两点：

1. 若 $G$ 存在增广路，则 $G'$ 也存在；
2. 若 $G'$ 存在增广路，则 $G$ 也存在。

设非树边（形成奇环的那条边）为 $(u,v)$，定义花根（blossom base）$h=\mathrm{LCA}(u,v)$。奇环是交替的，且有且仅有 $h$ 的两条邻边类型相同（都是非匹配边）；进入 $h$ 的树边必然是匹配边，环上除 $h$ 以外的其他点往环外的边都是非匹配边。

观察可知，从环外的边出去有两种走法：顺时针或逆时针，但两种走法在缩花后等价：

于是，缩花与不缩花都不影响最终增广路的正确性，我们可以放心地把奇环收缩成一个点继续搜索。

实现技巧：实作上找到「花」以后，我们不需要真的把图重建一次（那会带来高昂的开销），可以用一个数组记录每个点当前属于以哪个点为根的那朵花（即代码中的orig数组），在逻辑上完成缩花即可。

复杂度分析

• 每次找增广路需要遍历所有边，遇到「花」时要维护花上的点，单次复杂度 $O(|E|^2)$；
• 枚举所有未匹配点尝试增广，总共 $O(|V||E|^2)$。

带花树的 C++ 参考实现

仓库中的完整可运行实现位于 docs/graph/code/graph-matching/general-match/general-match_1.cpp，核心函数find_max_unweighted_matching由五个 Lambda/函数构成：

• lca(v, u)：利用时间戳aux数组求两个点在交错树上的最近公共祖先（即花根 $h$）。从两个端点交替向上沿orig[parent[match[v]]]跳，率先遇到已打上本轮时间戳的点即为 LCA。
• blossom(v, u, a)：以a为花根执行缩花。沿parent回溯，将环上所有点的orig统一改为a；若遇到标记为「i」的点则改为「o」并重新入队，使花内未扩展的分支继续扩展。
• augment(v)：沿parent链做增广，将匹配边与非匹配边逐段取反。
• bfs(root)：从根开始 BFS 构建交错树。label数组用 0 表示「o」、1 表示「i」、-1 表示未拜访；找到标记同为「o」且不属于同一朵花的点对时，即发现奇环，调用lca与两次blossom完成缩花。
• greedy()：在正式增广前先用随机顺序做一轮贪心匹配，作为初始匹配，减少后续 BFS 的次数（随机种子在实现中固定为114514，注释说明其值无关紧要）。

main函数从标准输入读取n（点数）与m（边数），边以 0-based 存储，输出最大匹配边数以及每个点的匹配对象（match[i] + 1，未匹配点输出 0）。图中undirectedgraph类以边编号方式存图，无向边只存一份，遍历时通过e.from ^ e.to ^ v快速求出另一端点。

基于高斯消元的一般图匹配算法

带花树虽然经典，但实现细节多、不易调试。OI-wiki 的这篇文档还介绍了一条完全不同的代数路线：基于高斯消元与 Tutte 矩阵的一般图匹配算法。与带花树相比，它的优势在于更易于理解与编写，同时便于解决「最大匹配中的必须点」等衍生问题；缺点在于常数较大——高斯消元的 $O(n^3)$ 基本是跑满的，而带花树一般跑不满。

阅读本节前，建议先复习仓库中「线性代数」部分的矩阵知识：docs/math/linear-algebra/matrix.md、docs/math/linear-algebra/determinant.md、docs/math/numerical/gauss.md。

前置知识：Tutte 矩阵

定义：对于 $n$ 个点的无向图 $G=(V,E)$，其 Tutte 矩阵 $\tilde A(G)$ 是一个 $n\times n$ 的矩阵，其中

$$ \tilde A(G){i,j} = \begin{cases} x{i,j}, & i<j,; (v_i, v_j)\in E \ -x_{i,j}, & i > j,; (v_i, v_j) \in E \ 0, & \text{otherwise} \end{cases} $$

其中 $x_{i,j}$ 是一个变量，因此 $\tilde A(G)$ 中共有 $|E|$ 个变量。在无歧义的情况下，以下将 $\tilde A(G)$ 简写为 $\tilde A$。

Tutte 定理：$G$ 存在完美匹配当且仅当 $\det \tilde A \ne 0$。

证明的思路是引入偶环覆盖的概念：一个无向图 $G$ 的偶环覆盖指用若干偶环（包括二元环）不重不漏地覆盖所有点。首先，$G$ 存在完美匹配当且仅当 $G$ 存在偶环覆盖：若存在偶环覆盖，每个环隔一条取一条边即得完美匹配；若存在完美匹配，将匹配边对应的二元环取出即得偶环覆盖。

再看行列式的定义：

$$ \det A = \sum_{\pi} (-1)^{\pi} \prod_{i} A_{i, \pi_i} $$

其中 $\pi$ 是任意排列，$(-1)^{\pi}$ 表示逆序对数为奇数时取 $-1$，否则取 $1$。每个排列都可看作 $G$ 的一个环覆盖；若环覆盖中存在奇环，将这个环翻转后（对应排列符号取反的项）求和一定为 0，因此只有偶环覆盖才能使行列式不为 0，证毕。

进一步地，$\operatorname{rank}\tilde A$ 一定为偶数，且 $G$ 的最大匹配大小等于 $\operatorname{rank}\tilde A$ 的一半。这由反对称矩阵的秩只能是偶数以及完美匹配的构造可得。

随机化取值与概率保证

实际应用中不可能带着 $|E|$ 个变量计算，做法是取一个素数 $p$ 的剩余系 $\mathcal{Z}_p$，把变量分别随机替换为 $\mathcal{Z}_p$ 中的数再计算（无歧义时下文仍用 $\tilde A$ 指代替换后的矩阵）。

定理：$\operatorname{rank}\tilde A$ 至多为 $G$ 最大匹配大小的两倍，且二者相等的概率至少为 $1-\frac{n}{p}$。考虑到一般图最大匹配中 $n$ 基本不会超过 $10^3$，实际取 $p$ 为 $10^9$ 数量级的素数即可（如实现中的 $p=10^9+7$）。

由该定理，若只需最大匹配数、无需匹配方案，只需做一次高斯消元求出 $\operatorname{rank}\tilde A$ 即可，远比带花树简洁；但若要输出匹配方案，则需要下面介绍的算法。

构造完美匹配

由 Tutte 定理，若 $G$ 存在完美匹配，则 $\tilde A$ 有很大概率满秩（下文叙述中省略「有很大概率」）。

记 $G$ 中标号为 $i$ 的点为 $v_i$，有如下定理：

定理：$\tilde A^{-1}_{j,i} \ne 0 \iff G-{v_i, v_j}$ 有完美匹配。

利用伴随矩阵的性质（若 $A$ 可逆，则 $A^{-1}=\frac{1}{\det A}A^*$），$\tilde A^{-1}{j,i}\ne 0$ 等价于 $\tilde A$ 删去第 $i$ 行第 $j$ 列后的子矩阵满秩。换言之，若 $(v_i, v_j)\in E$ 且 $\tilde A^{-1}{j,i}\ne 0$，就表明存在一个包含 $(v_i, v_j)$ 这条边的完美匹配方案，这样的边称为可行边。

由此可得到一个朴素的暴力算法：每次枚举 $i,j$，若 $(v_i,v_j)$ 是可行边，就将其加入匹配方案，在 $G$ 中删掉这两个点，再重新计算新的 $\tilde A^{-1}$。这样总共 $\frac n 2$ 轮，每轮 $O(n^3)$，总复杂度 $O(n^4)$，偏慢。

优化关键在于消去定理：令

$$ A = \begin{bmatrix} a_{1,1} & v^T \ u & B \end{bmatrix} \quad A^{-1} = \begin{bmatrix} \hat a^{1,1} & \hat v^T \ \hat u & \hat B \end{bmatrix} $$

若 $\hat a_{1,1}\ne 0$，则

$$ B^{-1} = \hat B - \frac{\hat u \hat v^T}{\hat a_{1,1}} $$

该定理描述的是消去第一行第一列的情形，可显然推广到任意一行一列。因此只需在算法最开始做一次 $O(n^3)$ 的求逆，之后每次删除两个点时各执行一次 $O(n^2)$ 的消去即可，总复杂度降为 $O(n^3)$。核心消去操作的示意代码（仓库文档内给出）：

void eliminate(int A[][MAXN], int r, int c) { // 消去第 r 行第 c 列 row_marked[r] = col_marked[c] = true; // 已经被消掉 int inv = quick_power(A[r][c], p - 2); // 逆元 for (int i = 1; i <= n; i++) if (!row_marked[i] && A[i][c]) { int tmp = (long long)A[i][c] * inv % p; for (int j = 1; j <= n; j++) if (!col_marked[j] && A[r][j]) A[i][j] = (A[i][j] - (long long)tmp * A[r][j]) % p; } }

其中row_marked/col_marked标记已消去的行列，逆元可用快速幂（费马小定理）求出。

构造最大匹配

上面的算法解决的是完美匹配，而题目一般要求最大匹配。前面已指出，$G$ 的最大匹配大小等于 $\operatorname{rank}\tilde A$ 的一半。如果能找到 $\tilde A$ 的一个最大满秩子方阵，那么对子方阵对应的导出子图求一组完美匹配，就得到了 $G$ 的一组最大匹配。

换一个角度：若 $G$ 有完美匹配，则 $\tilde A$ 满秩（行/列线性无关）；若 $\tilde A$ 不满秩，可求出 $\tilde A$ 的一组线性基，只保留线性基对应的行列，就得到一个最大满秩子方阵。求出最大满秩子方阵后，再用上面的算法求导出子图的完美匹配即可。注意：高斯消元过程中可能有行交换，实现时要维护好点的编号（见下面的id数组）。

完整实现解析

仓库中的完整实现位于 docs/graph/code/graph-matching/general-match/general-match_2.cpp，流程为：

1. 读入 $n,m$，对每条边 $(x,y)$ 令A[x][y] = rng() % p、A[y][x] = -A[x][y]，构造随机化的 Tutte 矩阵（constexpr int MAXN = 505, p = (int)1e9 + 7;）；
2. Gauss(A, nullptr, n)只求秩，利用高斯消元后主元位置找出一个极大满秩子矩阵，顶点记录在vertices中、编号映射存于id（因为消元时交换过列）；
3. 将满秩子矩阵对应的子矩阵拷出，Gauss(A, B, sub_n)求逆矩阵 $B=\tilde A^{-1}$；
4. 枚举满秩子矩阵内的点对 $(i,j)$：若t[vertices[i]][vertices[j]]（原邻接矩阵）非零且B[j][i]非零，则该边为可行边，将其加入匹配（girl数组记录匹配点），并调用两次eliminate(i, j)、eliminate(j, i)在 $O(n^2)$ 内更新逆矩阵；
5. 输出sub_n / 2与每个点的匹配对象。

测试样例 docs/graph/examples/graph-matching/general-match/general-match_2.in 为 $n=10,m=16$ 的一般图，对应的 答案 为匹配数 5，且两种算法（带花树与高斯消元）给出的具体匹配方案可以不同——这正说明了最大匹配不唯一，但匹配大小唯一。

实战：输入输出格式与验证

两道算法共用的输入格式（UOJ #79 风格）为：第一行两个整数 $n,m$，接下来 $m$ 行每行两个整数表示一条无向边。输出为两行：第一行最大匹配边数，第二行 $n$ 个整数表示每个点匹配的点编号（无匹配输出 0）。

配套测试数据位于 docs/graph/examples/graph-matching/general-match/，其中general-match_1.in对应带花树实现、general-match_2.in对应高斯消元实现，两者的答案文件可交叉验证输出格式。

习题推荐（可在在线评测系统中搜索）：

• UOJ #79 一般图最大匹配（本题是两类算法的标准验证场，建议两种实现都交一遍，体会常数与代码量差异）；
• UOJ #171【WC2016】挑战 NPC（一般图匹配的经典应用，需要将原问题建模为一般图最大匹配）。

小结

本文完整梳理了 OI-wiki 中一般图最大匹配的两条技术路线：

带花树以其稳定的实际表现成为竞赛中的首选；而高斯消元路线则提供了更易写、易扩展的备选方案。理解「奇环为什么难、缩花为什么对」以及「行列式/逆矩阵为什么能刻画匹配」，是打通这两类算法内在联系的关键。进一步深入可继续阅读仓库中 docs/graph/graph-matching/bigraph-match.md（二分图最大匹配）、docs/graph/graph-matching/bigraph-weight-match.md（二分图最大权匹配）与 docs/graph/graph-matching/general-weight-match.md（一般图最大权匹配）等姊妹篇文档。

参考资料

1. Mucha M, Sankowski P. Maximum matchings via Gaussian elimination.
2. 周子鑫，杨家齐《基于线性代数的一般图匹配》.
3. ZYQN《基于线性代数的一般图匹配算法》.

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