對于一般的二分圖匹配我們肯定會想到匈牙利算法，但是如果圖中出現(xiàn)奇環(huán)怎么辦？此時匈牙利算法就不可以了，就需要另一個算法：帶花樹算法
主要就是為了解決奇環(huán)的問題
我們匹配時會發(fā)現(xiàn)，如果存在奇環(huán)，傳統(tǒng)的匈牙利算法在一個奇環(huán)里至少有一個點(diǎn)不能匹配，那么干脆就把這個奇環(huán)縮成一個點(diǎn)（也叫開花，這就是算法名字的由來），在處理到奇環(huán)的時候把它縮成一個點(diǎn)，路徑取反的時候再暴力展開一個個取反。
縮點(diǎn)用并查集來維護(hù)

流程：

參考代碼
我們給所有點(diǎn)黑白染色。假設(shè)開始增廣的點(diǎn)是黑點(diǎn)。把所有黑點(diǎn)壓進(jìn)隊(duì)列中順次處理。對于一個黑點(diǎn)u，找與他相鄰的點(diǎn)v，會出現(xiàn)一下四種情況：

1、u,v已經(jīng)被縮成一個點(diǎn)了（這兩個點(diǎn)在一朵花里），跳過。

2、v是白點(diǎn)，說明已經(jīng)被匹配了，也就是偶環(huán)，跳過。

3、v還沒有被染色。那就先把這個點(diǎn)染成白的，然后嘗試與u匹配。如果v還沒有匹配就匹配上，增廣成功，然后沿增廣路取反。如果v已經(jīng)被匹配了，那么匹配他的點(diǎn)就是個黑點(diǎn)，染色，然后壓進(jìn)隊(duì)列。

4、v也是黑點(diǎn)。這時候染色發(fā)生了沖突，說明遇見了奇環(huán)。這時候就需要找到兩個點(diǎn)在帶花樹中的lca，然后把這整個環(huán)縮成一個點(diǎn)。（直接開花。）

縮點(diǎn)（開花）過程：
１、找x和y的LCA（的根）L。找LCA可以用各種方法。。。直接樸素也行。
２、在pre數(shù)組中把x和y接起來（表示它們形成環(huán)了！）
3、從x、y分別走到L，維護(hù)并查集使得變成一棵樹，同時沿路把pre數(shù)組連接起來。

題目：

UOJ79 一般圖最大匹配
從前一個和諧的班級，所有人都是搞OI的。有 n 個是男生，有 0 個是女生。男生編號分別為 1,…,n。
現(xiàn)在老師想把他們分成若干個兩人小組寫動態(tài)仙人掌，一個人負(fù)責(zé)搬磚另一個人負(fù)責(zé)吐槽。每個人至多屬于一個小組。
有若干個這樣的條件：第 v 個男生和第 u 個男生愿意組成小組。
請問這個班級里最多產(chǎn)生多少個小組？

題解：

就是帶花樹的模板題

代碼：

#include <bits/stdc++.h> #define ll long long using namespace std; const int N = 510; const int M = 3e5+10; struct node{ int to,nxt; }g[M]; int head[N],cnt; int vis[N],match[N],f[N],pre[N],Id,id[N]; //vis[i]: 0(未染色) 1(黑色) 2(白色) //match[i]: i的匹配點(diǎn) //f[i]: i在帶花樹中的祖先 //pre[i]: i的非匹配邊的另一點(diǎn) //id: 找LCA用 int n,m,ans,u,v; queue<int> q; void Init() {Id=ans=cnt=0;for(int i=1;i<=n;i++)head[i]=-1,id[i]=match[i]=0; } void add(int u,int v){ g[cnt]=node{v,head[u]},head[u]=cnt++; } int getf(int x){ return f[x]==x?x:f[x]=getf(f[x]); } //查詢x和y在帶花樹中的LCA int LCA(int x,int y) {//沿著增廣路向上找lca for(++Id;;swap(x,y))//x,y交替向上 if(x){x=getf(x);//有可能環(huán)中有環(huán)(花中有花)，所以用并查集找祖先，只處理祖先節(jié)點(diǎn) if(id[x]==Id) return x; //x,y在同一環(huán)中，一定會找到已被編號的點(diǎn)，該點(diǎn)即為LCA。 else id[x]=Id,x=pre[match[x]];//給點(diǎn)編號，并沿著非匹配邊向上找 } } //縮點(diǎn)（開花 void blossom(int x,int y,int l)//，將x、y到LCA(l)路徑中的點(diǎn)，縮為一點(diǎn)int l) { while(getf(x)!=l){//增廣路取反 pre[x]=y;y=match[x];//如果x、y的奇環(huán)中有白點(diǎn)，將其染為黑點(diǎn)，放入隊(duì)列，讓其去找不是環(huán)中的匹配點(diǎn) if(vis[y]==2) vis[y]=1,q.push(y);//只改變是根的點(diǎn) if(getf(x)==x) f[x]=l;if(getf(y)==y) f[y]=l;//增廣路取反 x=pre[y];} } bool aug(int s) {//每次都以s為起點(diǎn)bfs，建帶花樹 for(int i=1;i<=n;i++)vis[i]=pre[i]=0,f[i]=i; while(!q.empty()) q.pop();q.push(s),vis[s]=1;while(!q.empty()){u=q.front();q.pop();for(int i=head[u];~i;i=g[i].nxt){v=g[i].to;//如果已經(jīng)在同一個環(huán)(花)中或者是白點(diǎn)(意為這已經(jīng)有匹配點(diǎn))，只接跳過 //這種情況不會增加匹配數(shù) if(getf(u)==getf(v)||vis[v]==2) continue;//如果沒有被染色 if(!vis[v]){//先染為白色，將前繼點(diǎn)指向u vis[v]=2;pre[v]=u;//如果沒有被匹配過，直接匹配成功 if(!match[v]){//增廣路取反 for(int x=v,last;x;x=last)last=match[pre[x]],match[x]=pre[x],match[pre[x]]=x; return 1;}//如果被匹配過，則把匹配v的點(diǎn)染為黑色，放入隊(duì)列中 vis[match[v]]=1;q.push(match[v]);}//v是黑色，形成奇環(huán)，則縮點(diǎn)(開花)。 else {int lca=LCA(u,v);blossom(u,v,lca);blossom(v,u,lca);}} }return 0; } int main(void) {while(~scanf("%d%d",&n,&m)) {Init();while(m--){scanf("%d%d",&u,&v);add(u,v),add(v,u); } for(int i=1;i<=n;i++)if(!match[i]&&aug(i))ans++; printf("%d\n",ans);for(int i=1;i<=n;i++)printf("%d%c",match[i]," \n"[i==n]);}return 0; } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的带花树算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。