一般图最大匹配完全指南带花树算法与基于高斯消元的新方法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$分为两种情况$u$ 未拜访过若 $u$ 是未匹配点则找到了增广路径否则从 $u$ 的配偶继续找增广路将其配偶标记为「o」并入队。$u$ 已拜访过若遇到标记为「o」的点说明遇到了奇环需要缩花shrink blossom否则遇到的是偶环直接跳过。遇到偶环时可以将其视为二分图情形处理因此可以忽略遇到奇环时则需要缩花在缩花后的新图中继续找增广路缩花的正确性两张图的增广路等价设原图为 $G$缩花后的图为 $G$只需证明两点若 $G$ 存在增广路则 $G$ 也存在若 $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}, ij,; (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$ 数量级的素数即可如实现中的 $p10^97$。由该定理若只需最大匹配数、无需匹配方案只需做一次高斯消元求出 $\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流程为读入 $n,m$对每条边 $(x,y)$ 令A[x][y] rng() % p、A[y][x] -A[x][y]构造随机化的 Tutte 矩阵constexpr int MAXN 505, p (int)1e9 7;Gauss(A, nullptr, n)只求秩利用高斯消元后主元位置找出一个极大满秩子矩阵顶点记录在vertices中、编号映射存于id因为消元时交换过列将满秩子矩阵对应的子矩阵拷出Gauss(A, B, sub_n)求逆矩阵 $B\tilde A^{-1}$枚举满秩子矩阵内的点对 $(i,j)$若t[vertices[i]][vertices[j]]原邻接矩阵非零且B[j][i]非零则该边为可行边将其加入匹配girl数组记录匹配点并调用两次eliminate(i, j)、eliminate(j, i)在 $O(n^2)$ 内更新逆矩阵输出sub_n / 2与每个点的匹配对象。测试样例 docs/graph/examples/graph-matching/general-match/general-match_2.in 为 $n10,m16$ 的一般图对应的 答案 为匹配数 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 中一般图最大匹配的两条技术路线对比维度带花树算法基于高斯消元的算法提出者 / 来源Jack Edmonds1961基于 Tutte 矩阵与线性代数核心思想奇环缩花 交错树增广随机化 Tutte 矩阵 秩与逆矩阵时间复杂度$O(|V||E|^2)$$O(n^3)$常数较大基本跑满实现难度细节多需维护花、LCA、缩花逻辑清晰易于编写与调试衍生能力直接输出方案便于处理「最大匹配中的必须点」等问题带花树以其稳定的实际表现成为竞赛中的首选而高斯消元路线则提供了更易写、易扩展的备选方案。理解「奇环为什么难、缩花为什么对」以及「行列式/逆矩阵为什么能刻画匹配」是打通这两类算法内在联系的关键。进一步深入可继续阅读仓库中 docs/graph/graph-matching/bigraph-match.md二分图最大匹配、docs/graph/graph-matching/bigraph-weight-match.md二分图最大权匹配与 docs/graph/graph-matching/general-weight-match.md一般图最大权匹配等姊妹篇文档。参考资料Mucha M, Sankowski P. Maximum matchings via Gaussian elimination.周子鑫杨家齐《基于线性代数的一般图匹配》.ZYQN《基于线性代数的一般图匹配算法》.【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 一般图最大匹配完全指南：带花树算法与基于高斯消元的新方法（OI-wiki 实战解析）
一般图最大匹配完全指南带花树算法与基于高斯消元的新方法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$分为两种情况$u$ 未拜访过若 $u$ 是未匹配点则找到了增广路径否则从 $u$ 的配偶继续找增广路将其配偶标记为「o」并入队。$u$ 已拜访过若遇到标记为「o」的点说明遇到了奇环需要缩花shrink blossom否则遇到的是偶环直接跳过。遇到偶环时可以将其视为二分图情形处理因此可以忽略遇到奇环时则需要缩花在缩花后的新图中继续找增广路缩花的正确性两张图的增广路等价设原图为 $G$缩花后的图为 $G$只需证明两点若 $G$ 存在增广路则 $G$ 也存在若 $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}, ij,; (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$ 数量级的素数即可如实现中的 $p10^97$。由该定理若只需最大匹配数、无需匹配方案只需做一次高斯消元求出 $\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流程为读入 $n,m$对每条边 $(x,y)$ 令A[x][y] rng() % p、A[y][x] -A[x][y]构造随机化的 Tutte 矩阵constexpr int MAXN 505, p (int)1e9 7;Gauss(A, nullptr, n)只求秩利用高斯消元后主元位置找出一个极大满秩子矩阵顶点记录在vertices中、编号映射存于id因为消元时交换过列将满秩子矩阵对应的子矩阵拷出Gauss(A, B, sub_n)求逆矩阵 $B\tilde A^{-1}$枚举满秩子矩阵内的点对 $(i,j)$若t[vertices[i]][vertices[j]]原邻接矩阵非零且B[j][i]非零则该边为可行边将其加入匹配girl数组记录匹配点并调用两次eliminate(i, j)、eliminate(j, i)在 $O(n^2)$ 内更新逆矩阵输出sub_n / 2与每个点的匹配对象。测试样例 docs/graph/examples/graph-matching/general-match/general-match_2.in 为 $n10,m16$ 的一般图对应的 答案 为匹配数 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 中一般图最大匹配的两条技术路线对比维度带花树算法基于高斯消元的算法提出者 / 来源Jack Edmonds1961基于 Tutte 矩阵与线性代数核心思想奇环缩花 交错树增广随机化 Tutte 矩阵 秩与逆矩阵时间复杂度$O(|V||E|^2)$$O(n^3)$常数较大基本跑满实现难度细节多需维护花、LCA、缩花逻辑清晰易于编写与调试衍生能力直接输出方案便于处理「最大匹配中的必须点」等问题带花树以其稳定的实际表现成为竞赛中的首选而高斯消元路线则提供了更易写、易扩展的备选方案。理解「奇环为什么难、缩花为什么对」以及「行列式/逆矩阵为什么能刻画匹配」是打通这两类算法内在联系的关键。进一步深入可继续阅读仓库中 docs/graph/graph-matching/bigraph-match.md二分图最大匹配、docs/graph/graph-matching/bigraph-weight-match.md二分图最大权匹配与 docs/graph/graph-matching/general-weight-match.md一般图最大权匹配等姊妹篇文档。参考资料Mucha M, Sankowski P. Maximum matchings via Gaussian elimination.周子鑫杨家齐《基于线性代数的一般图匹配》.ZYQN《基于线性代数的一般图匹配算法》.【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考