花树

带花树算法（⼀般图最⼤匹配）

我们⾸先介绍匈⽛利算法，它可以处理不存在奇环的⼆分图图最⼤匹配问题，但是，当它处理含奇环的⼀般图时，要么⽆法保证复杂度，要

么⽆法保证正确性。

因此，我们有了带花树算法

它的过程和匈⽛利算法类似，只是加⼊了处理奇环（这⾥称为花）的情况。

⾸先，依次枚举每个点，找出未匹配的点s，将s染成蓝⾊，加⼊队列（使⽤宽搜），从s出发寻找增⼴路。

对于队列⾥的x，枚举它的邻居y，有以下⼏种情况

1.若y未匹配，则找到增⼴路

2.若y已匹配：

1）y未染⾊：将y染为红⾊，将y的匹配点染为蓝⾊，并加⼊队列

2）y染红⾊：说明遇到偶环，⽆需处理

3）y染蓝⾊：说明遇到奇环

此时，需要⽤并查集进⾏缩点操作，将花上的点加⼊队列（此时花上所有点都可以进⾏扩展），并全部染成蓝⾊。

关于缩点的正确性，我们可以考虑奇环上的任意⼀个点，它与花柄共同将花分成⼀个奇链和偶链，⽽那个偶链必然可以作为增⼴路的⼀部分

（可以⾃⼰画图看看），于是，我们不需要考虑花内点的⾛向，便可以将其缩为⼀个点。

然⽽，当我们找到⼀个增⼴路时，需要构造路径，于是我们⽤⼀个pre数组记录路径信息。

在奇环外，pre即为上⼀个到达它的点：（绿⾊即为pre）

在奇环内，由于不知道增⼴路的⾛向，我们需要建⽴双向pre（可以⾃⼰举⼏个例⼦体会）：

可能有⼈会疑问，花柄的pre应该指向谁？对于上⾯那幅图，花柄pre的指向⽆所谓，因为到它时，必然会⾛匹配边。但是，对于下⾯这种花

套花的情况，花柄的pre在之前的花中已经处理好，也不需要管它。

4）若x，y已经缩成⼀点，则不必处理

⾃此，主要过程已经结束，可以看下具体代码：

寻找花柄（即搜索树上的lca）

x与y轮流向上跳，第⼀个重叠处即为lca，其中getfa操作⽬的是省去跳花内的边，保证每个边只会跳⼀次，保证复杂度

intlca(intx,inty){

++cnt;x=getfa(x);y=getfa(y);//getfa即找当前点属于的花的花柄

while(v[x]!=cnt){

v[x]=cnt;

x=getfa(pre[match[x]]);

if(y)swap(x,y);//y还没跳到根

}

returnx;

}

建⽴双向pre

voidmodify(intx,intlc){

while(x!=lc){

intmx=match[x],p=pre[mx];

(mx);col[mx]=1;

fa[x]=fa[mx]=lc;

if(getfa(p)==lc)return;//不管花柄

pre[p]=mx;//另⼀⽅向在bfs时已建⽴

x=p;

}

}

intlc=lca(x,y);

if(getfa(x)!=lc)/*不管花柄*/pre[x]=y;if(getfa(y)!=lc)/*不管花柄*/pre[y]=x;

modify(x,lc);modify(y,lc);

主过程bfs

intsol(ints){

while(!())();

cnt=0;

for(inti=1;i<=n;++i)fa[i]=i,pre[i]=col[i]=v[i]=vis[i]=0;

(s);col[s]=1;vis[s]=1;

while(!()){

intx=();();

for(inti=la[x];i;i=g[i].nxt){

inty=g[i].y;

if(getfa(x)==getfa(y))continue;

if(col[y]==0){

col[y]=2;pre[y]=x;

if(match[y]==0){//找到增⼴路

while(x!=s){

intz=match[x];

match[x]=y;match[y]=x;

x=pre[z];y=z;

}

match[x]=y;match[y]=x;

return1;

}elif(vis[match[y]]==0){col[match[y]]=1;vis[match[y]]=1;(match[y]);}

}elif(col[y]==1){

intlc=lca(x,y);

if(getfa(x)!=lc)pre[x]=y;if(getfa(y)!=lc)pre[y]=x;

modify(x,lc);modify(y,lc);

}

}

}

return0;

}