花樹

帶花樹算法（?般圖最?匹配）

我們?先介紹匈?利算法，它可以處理不存在奇環的?分圖圖最?匹配問題，但是，當它處理含奇環的?般圖時，要么?法保證復雜度，要

么?法保證正確性。

因此，我們有了帶花樹算法

它的過程和匈?利算法類似，只是加?了處理奇環（這?稱為花）的情況。

?先，依次枚舉每個點，找出未匹配的點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;

}