带花树学习笔记

· · 个人记录

在下文中，虚边默认是非匹配边，实边默认是匹配边。

路径取反的意思是，把路径上点匹配边变成非匹配边，非匹配边变成匹配边。

核心思想

类似于二分图匹配，一般图匹配也是找交替链形成的增广路不断增广，但是因为图中可能存在奇环，二分图中无脑交替跳边和记忆化都不能使用。

如图。如果像二分图一样无脑交替跳边，可能会走出图中红绿交替的路径，这样看似找到了一条增广路，但实际上这条路不能进行增广，因为 (2,3) 这条匹配边正反各走了一次，增广之后结点 3 的匹配将不合法。而在二分图中，所有的匹配边都只能沿着一个方向走，所以可以无脑交替跳边。

而按照二分图的做法，当我们沿着 1-2-3-5 的搜索没找到增广路时，会把 1-2-3-5 都禁用掉，但实际上图中有 1-2-3-4-5-7 的增广路。而在二分图中不会出现这种情况。

即使这样，我们还是可以从二分图找增广路的思路出发，尝试加上一些别的操作使得一般图也可以正确地找到增广路。

首先考虑处理奇环。不难发现的是，只有形如边数为 2k+1 且有 k 个匹配的奇环会对求增广路有影响，考虑分析这种奇环的性质。

可以发现，在这种限制下，环中有且仅有一个点可以和环外匹配，且环内任意点都可以成为这个点。

如图，这是我们需要的一个奇环。这个时刻有且仅有 1 可以和环外匹配。假设我们要让 4 和环外匹配，直接对路径 1-5-4 取反即可。这时候有且仅有 4 可以和环外匹配。不难发现的是所有环上的点都可以通过这么操作实现。

也就是说环这个整体和一个点的本质没有什么区别——和外界有且仅有一个匹配。

所以这时候我们直接把这个环缩成一个点即可，这个过程被称作开花。其中最上面的点叫做花根（然后图上就有花了，而找增广路会形成一个交替链构成的树，所以带花树就是有花的树）

这就是带花树的核心思想——在找增广路的途中如果碰到了一个奇环就把奇环缩成一个点，然后继续找。找到增广路之后就直接增广，如果一个点就是点就直接改匹配边，如果一个点是花就展开，然后在内部把它向外界的连边调整到需要的状态再改匹配边。

完结撒花。

具体实现

带花树的思想是非常直接的——分析奇环的性质然后做出相应措施。但是带花树算法的代码实现复杂度比较高。

我们把带花树的算法流程分成找树——开花——增广三个流程。

找树

首先我们选择的找增广路的方式应该是 bfs 而不是 dfs。因为在找到花之后，我们需要缩点，缩点后如果用 dfs 边的处理会比较麻烦。

在 bfs 的时候我们给每个点一个 tag，表示这个点的属性，它的意义是这个点的父边是匹配边还是非匹配边，假设前者为 2 后者为 1，并钦定根的 tag 为 1，这也相当于做了一遍黑白染色。

在扩张交替树的时候，就可以直接通过下一个点的 tag 来判断交替树接下来的状态。一共有以下几种情况：

  1. 下一个点没有 tag，且它没有匹配。那么就找到了一条增广路。
  2. 下一个点没有 tag，且它有匹配。那么直接把它和它的匹配点加入交替树，并且把它的匹配点加入 bfs 的队列（因为边状态的交替性，所以放下一个点的匹配点）。
  3. 下一个点有 tag，且它和当前点在同一个花中。花内只需要留下一个大环即可，剩下的边无所谓，直接忽略。
  4. 下一个点有 tag，且它和当前点的 tag 不同。那么就找到了一个偶环，直接忽略。
  5. 下一个点有 tag，且它和当前点的 tag 相同。那么就找到了一个奇环，直接开花。

这样我们就可以通过 bfs 求交替树来找增广路。

开花

当碰到一个奇环的时候我们需要开花。为了方便，缩点我们并不进行直接缩点，而是用并查集维护每个点当前的花根是什么。为了方便，每个点一开始就是一朵花，它自己是花根。

在找到奇环之后我们需要开花。假设最后的一条边是 (u,v)，不难发现花根会是 u,v 在交替树上的 LCA，这里的 LCA 是缩点后的 LCA，也就是说 LCA 一定是一个花根。因为整个算法的时间复杂度瓶颈不在这里，所以我们可以通过暴力直接求得它。

找到花根 l 之后就需要把 u-l,v-l 这两个路径上面的点都缩到花根上去。

那么我们直接扫暴力从 u,v 跳到 l，然后把路径上面的花根的并查集指到 l 上。（当然，我们可以把路径上所有点的并查集都指到 l 上，因为路径上所有点的花根都在路径上，但是根据定义，只有花根是真实存在的，而其它点已经被缩进了花中），然后因为缩了点，所以之前没有遍历的点的边（也就是 tag 为 2 的点的边）需要遍历一遍，所以我们直接把这些点的 tag 改成 1 并且加入 bfs 队列。

这样我们就完成了开花的操作。

增广

其实上面几个都比较简单，主要难点是在增广上。

假设点 x 的匹配点是 match[x]。那么在增广的时候，所有走匹配边就直接走 match 即可，主要问题是在非匹配边上，设它为 pre。

在扩展 bfs 交替树的时候，假设当前在扫 x 的出边，而扫到的点是 y，在 y 没有 tag 的时候我们直接把 y 的 pre 设为 x 即可，因为只能这么增广。

难点是在开花的时候怎么维护 pre。

因为在没有奇环的时候，增广可以看成是在交替树上一条叶子到根的链。深度为奇数的点往上跳是跳 match 边，不需要 pre 所以这些点没有 pre。

但是在花上不一样，因为走花有两种走法，且两种走法对于一个点来说走的边的类型是不同的。所以在开花的时候，我们需要遍历花，并且更新路径上面点的 pre 以确保可以走类型不同的路到达花根。

如图，增广路是 1-2-3-5-4-6。但实际上在 bfs 的时候只有 pre[4]=1,pre[6]=4,pre[2]=1 ，而增广的时候我们需要用到 (5,3) 这条边，而我们没有记录。 因为在 bfs 过程中我们记录的仅仅是直接往上走得到的 pre，而往下走没有记录。

所以在开花的时候把向下走的 pre 也更新一下即可。

但这样会产生一个问题，就是更新 pre 可以看成是把花上面的 pre 边全部变成了双向的（往上走 pre[x]=y 那么往下走 pre[y]=x）。但是如果一个点被多个花包含，可以往下的走的点可能会有很多

如图，这里交替树视为不包括 (4,6)(6,9) 的树，那么对于 6 而言，它在上面的环中的 pre 应该是 4 而在下面的环中的 pre 应该为 9 。

————还没写完先咕着————