带花树？错了，是开花算法（ Blossom Algorithm \text{Blossom Algorithm} Blossom Algorithm）。
在维基百科上有漂亮的图片。 OI-wiki \text{OI-wiki} OI-wiki 中也是使用的这些图片。
在 C F \rm CF CF 的帖子里有很好的叙述，可供参考。
称邻边都未匹配的点为 e x p o s e d \rm exposed exposed，裸露的。首先，最大匹配等价于图中没有增广路，其中增广路是两个端点都 e x p o s e d \rm exposed exposed 且路径上的边的匹配情况交错。并且增广不会让之前不能增广的裸露点变得可增广，否则两条增广路的对称差（的俩连通块之一）是原本就可行的增广路。
因此我们可以从每个裸露点开始，找增广路。走增广路过程中走出的奇环被称作花（ blossom \text{blossom} blossom）。花上没有裸露点，且仅有一个点的两条环上邻边都未匹配，称为花心。那么所有经过花的增广路必然经过花心。而且，花心到花上点有两种走法，必有其中之一能使得路径交错。因此花可以被 c o n t r a c t \rm contract contract 。
缩 b l o s s o m \rm blossom blossom 会嵌套；没有花时，图是二部图，增广路可以求解。
难点大概在于，怎样得到原图上的增广路。精细实现的复杂度应该可以做到 O ( n 3 ) \mathcal O(n^3) O(n3)，但因为我没实现过，所以我也不清楚。
可见
C
F
\rm CF
CF 帖子的评论区，和
2017
2017
2017 年论文《基于线性代数的一般图匹配》。引入
Tutte
\text{Tutte}
Tutte 矩阵
A
~
(
G
)
\tilde A(G)
A~(G) 满足
A
~
i
,
j
=
{
x
i
,
j
e
i
,
j
(
i
<
j
)
0
(
i
=
j
)
−
x
j
,
i
e
j
,
i
(
j
<
i
)
\tilde A_{i,j}=
其中 e i , j e_{i,j} ei,j 表示 i , j i,j i,j 之间是否有连边，而 x i , j x_{i,j} xi,j 是形式变元。
动机是 det A ~ ≠ 0 \det\tilde A\ne 0 detA~=0 足以说明图中有完美匹配。因为行列式的定义相当于作环覆盖，存在奇环时，将环反向可以使值抵消；不存在奇环时，可以构造出匹配。
判定 det A ~ ≠ 0 \det\tilde A\ne 0 detA~=0 利用随机化赋值，根据 Schwartz–Zippel \text{Schwartz–Zippel} Schwartz–Zippel 引理，错误的概率不超过 deg det A ~ p = O ( n p ) {\deg\det\tilde A\over p}=\mathcal O({n\over p}) pdegdetA~=O(pn) 可以接受，其中 F p \mathbb{F}_p Fp 为随机范围。
考虑最大匹配。只需找出列 r a n k \rm rank rank，因为这些位置构成的主子式非零（别忘了 A ~ \tilde A A~ 是 斜对称 的）。所以，求最大匹配的值，已经有了 O ( n ω ) \mathcal O(n^\omega) O(nω) 的做法。
Comment. 其中 O ( n ω ) \mathcal O(n^\omega) O(nω) 表示矩阵乘法 / / / 消元的复杂度。
Remark. 消元可以和矩阵乘法做到相同复杂度，但不是高斯消元。而且具体实现我也不会，据称巨复杂。所以我们也可以不管它 😄
同时我们证明了 det A ~ ≠ 0 \det\tilde A\ne 0 detA~=0 必然有 2 ∣ n 2\mid n 2∣n 。因为必须避免奇环。
构造解，不妨假定
det
A
~
≠
0
\det\tilde A\ne 0
detA~=0 。有个神奇的性质是
det
A
{
i
}
,
{
j
}
≠
0
⟺
det
A
{
i
,
j
}
,
{
i
,
j
}
≠
0
\det A^{\{i\},\{j\}}\ne 0\iff\det A^{\{i,j\},\{i,j\}}\ne 0
detA{i},{j}=0⟺detA{i,j},{i,j}=0
Comment. 由于麻烦，下面的一小段中漏掉了波浪线符号。
其中 det A S , T \det A^{S,T} detAS,T 表示 A A A 去掉 S S S 中的行、 T T T 中的列的余子式。
证明充分性：因为 rank A { i } , { j } = n − 1 \operatorname{rank}A^{\{i\},\{j\}}=n-1 rankA{i},{j}=n−1 因此 rank A { i , j } , { i , j } ⩾ n − 3 \operatorname{rank}A^{\{i,j\},\{i,j\}}\geqslant n-3 rankA{i,j},{i,j}⩾n−3，而斜对称矩阵的秩必然是偶数。
证明必要性：则列 rank A { i , j } , { j } = n − 2 \operatorname{rank}A^{\{i,j\},\{j\}}=n-2 rankA{i,j},{j}=n−2，故行 rank A { j } , { j } = n − 2 \operatorname{rank}A^{\{j\},\{j\}}=n-2 rankA{j},{j}=n−2，即 A ∅ , { j } A^{\varnothing,\{j\}} A∅,{j} 中第 i i i 行可被其他行线性表出，然后 rank A { i } , { j } = rank A ∅ , { j } = n − 1 \operatorname{rank}A^{\{i\},\{j\}}=\operatorname{rank}A^{\varnothing,\{j\}}=n-1 rankA{i},{j}=rankA∅,{j}=n−1，即证。
然后，显然 det A { i , j } , { i , j } ≠ 0 \det A^{\{i,j\},\{i,j\}}\ne 0 detA{i,j},{i,j}=0 则存在包含 ⟨ i , j ⟩ \langle i,j\rangle ⟨i,j⟩ 的完美匹配，接下来把 i , j i,j i,j 删除继续递归。这只需判断 det A { i } , { j } \det A^{\{i\},\{j\}} detA{i},{j}，联想到伴随矩阵 A ∗ A^\ast A∗，由于斜对称性，不需额外转置。又联想到 A − 1 = A ∗ det A A^{-1}={A^\ast\over\det A} A−1=detAA∗，因此只需判断 ( A ~ − 1 ) i , j (\tilde A^{-1})_{i,j} (A~−1)i,j 是否非零即可。
需要动态维护矩阵的逆。利用这样的定理：若
A
=
(
a
ˉ
v
ˉ
u
ˉ
B
ˉ
)
,
A
−
1
=
(
a
v
u
B
)
A=
那么 B − 1 = B ˉ − u v a B^{-1}=\bar B-{uv\over a} B−1=Bˉ−auv 。其中 u u u 是 n × 1 n\times 1 n×1 矩阵， v v v 是 1 × n 1\times n 1×n 矩阵， a ≠ 0 a\ne 0 a=0 。
证明只需暴力展开，此处略。不难发现这就对应了删去（同标号）一行一列的维护。
而高斯消元的初等行变化可以很容易地同步作用到 A − 1 A^{-1} A−1 上，是可维护的。
显然每次维护是 O ( n 2 ) \mathcal O(n^2) O(n2) 的，共 n n n 次维护，总复杂度 O ( n 3 ) \mathcal O(n^3) O(n3) 无误。
如果带权呢？把 e i , j e_{i,j} ei,j 设为 y w i , j y^{w_{i,j}} ywi,j，转化为求算 det A ~ \det\tilde A detA~ 中 y y y 最高次数，用插值得到 关于 y y y 的结果。只在 ∑ w \sum w ∑w 较小时可用。
根据
Jack Edmonds
\text{Jack Edmonds}
Jack Edmonds 的研究1，最大匹配可以用如下线性规划得到：
{
∑
j
x
i
,
j
⩽
1
for all
i
∈
V
∑
i
,
j
∈
S
x
i
,
j
⩽
r
for all
r
⩽
∣
V
∣
,
∣
S
∣
=
2
r
+
1
x
i
,
j
⩾
0
for all
i
,
j
∈
V
他证明了该 L P \rm LP LP 的解空间（多胞体）的所有顶点恰为所有匹配。
NEED HELP. 他是怎样证明的？我现在还没看懂。😢
Maximum Matching and a Polyhedron With 0,1-Vertices. doi: 10.6028/jres.069.（科学上网访问速度更快） ↩︎