|
【图论】【一般图匹配】带花树算法详解
Singercoder
2020-04-06 20:27:58
Solution
# 算法介绍
+ 算法简介：带花树算法，是一种在一般图中寻找最大匹配的算法。它是以匈牙利算法为基础，并特别加入了对奇数环的讨论后形成的。
+ 前置知识：**bfs**匈牙利算法+并查集
# 模板分析
直接以[uoj79](http://uoj.ac/problem/79)为模板讲解。luogu数据过水，无法卡掉所有错误做法。
1. 创造性的算法往往是在已有基础上改进形成的，带花树算法亦是如此。
我们考虑在一个一般图中，不存在奇数环，即为一颗存在偶数环的树，可以想到直接对其进行二分图染色+匈牙利算法（二者可以同时进行）解决，这是带花树算法的基础框架。（code省略了部分细节）
```cpp
bool bfs(int s)
{
while(!q.empty())
{
u=q.front();q.pop();
for(int v=1;vN），而这条増广路是从花内距花根较远的一条路延伸来的（如图中J->I->H->N)。
3. 考虑如何记录这条较远的非常规路径。我们知道，在匈牙利算法中，对于每一对匹配中的入点v，我们都会有一个pre指向其前驱匹配的出点u（即图中的红色边），也就是说仅有v型点具有pre。
然而在花中，所有点可以作为u型点向外遍历，也就没有了严格的u、v区分。因此无论u、v染色情况如何，我们为花中所有匹配对之间建立相互的pre，具体实现见下（注意由于原本已有部分pre，即红色边，我们要根据特殊性质去建立剩余的pre，即蓝色边）。
特别注意，如果到了u为根节点，就不要再反向建立pre了，因为它所在匹配对并不完全属于花！
这样，无论以哪个点作为u向环外遍历，我们在花内部都能得到正确的増广路。（想一想，以图中表示出的白色点和绿色点分别为起点，向花外遍历，其在花内体现出的増广路分别是什么样的？）
```cpp
else//环
{
if(get_fa(u)==get_fa(v))continue;//该环已被缩成一点，不必处理
if(col[v]==1)//奇数环，需要将花缩成花根一点
{
//此时的u、v均为出点，不适用命名原则
int r=lca(u,v);//寻找lca，即总花根
shrink(u,v,r);//分别从两个方向，建立反向pre，保证花内部増广路正确性
shrink(v,u,r);
}
//偶数环不必处理
}
```
3. 你可能会注意到上面的程序框架中出现了lca和shrink这两个函数。
关于lca，我们只要朴素寻找总花根即可，因为遍历的起点总是在变的，无法用倍增lca来加速。
关于shrink，思想就是上述对于花内増广路的维护，也就是建立反向pre。
连带修改増广路的aug函数一起，code如下：
```cpp
void aug(int v)//从v点开始修改増广路
{
int t;
while(v)
{
t=match[pre[v]];//临时记录下一次的v
match[v]=pre[v];
match[pre[v]]=v;
v=t;
}
}
int cnt,vis[MAXN];
int lca(int u,int v)//寻找两个节点的总花根
{
++cnt;//每次lca选用不同的cnt作为判断条件
u=get_fa(u);//保证操作对象时刻为分花根
v=get_fa(v);
while(vis[u]!=cnt)//某一点同时两次被染色，即为总花根
{
vis[u]=cnt;
u=get_fa(pre[match[u]]);//保证操作对象时刻为分花根
if(v)swap(u,v);//切换操作对象
}
return u;
}
void shrink(int u,int v,int r)//以r为总花根，将花缩成花根一点，并建立内部的反向pre
{
while(get_fa(u)!=r)//当已达到总花根，说明缩花任务完成
{
//每次循环起初的v为上个匹配的v
pre[u]=v;//建立反向pre，保证増广路
v=match[u];
if(col[v]==2){col[v]=1;q.push(v);}//花内所有v，都应以u身份向外増广
if(get_fa(u)==u)fa[u]=r;//如果某一点为分花根，将其合并到总花根上
if(get_fa(v)==v)fa[v]=r;
u=pre[v];//切换操作对象
}
}
```
于是基础的匈牙利算法和对奇数环的讨论全部完成，带花树算法成功得到实现。
# 时间复杂度
+ 同匈牙利算法，O（$n^3$）。
不过常数肯定略大，且编程难度也大幅上升。
|