看了兩篇博客，覺得寫得不錯，便收藏之。。

　　首先是第一篇，轉自某Final牛

帶花樹……其實這個算法很容易理解，但是實現起來非常奇葩（至少對我而言）。

除了wiki和amber的程序我找到的資料看著都不大靠譜

比如昨晚找到一篇鄙視帶花樹的論文，然后介紹了一種O(E)的一般圖最大匹配……我以為找到了神論文，然后ACM_DIY眾神紛紛表示這個是錯的……于是神論文成為了”神論文“……

又比如圍觀nocow上帶花樹標程，一看……這顯然是裸的匈牙利算法……貨不對板啊

當然……如果二分圖的匈牙利算法還不會請先圍觀求二分圖最大匹配的匈牙利算法。

?

實際上任意圖求最大匹配也是找增廣路，但是由于奇環的出現，找增廣路變得困難。

首先明確一點，增廣路上是不能有重復出現的點的。

??
?

二分圖中，匹配邊可以看作是有向的，比如定義總是從X集指向Y集。假若定義了起點必須在X集中，那么增廣路中出現該匹配邊時，必然是按照這個方向的。所以一個點在增廣路中的奇偶性是確定的。

而這個圖中，從增廣路3->1->4->5和2->4->1->6可以看出，對于有奇環的任意圖，1和4這兩個點在增廣路中所在位置的奇偶性不再一定。于是我們考慮處理這些奇環。

?

定義奇環：包含2k+1個點和k條匹配邊的一個環。（如果不是這樣，我們找增廣路不會走上去）

對于這個奇環，k條匹配覆蓋了2k個點，那么顯然有一個點未被覆蓋。我們拿出這個點來討論。

比如圖中的1號點就是這個這個特殊的點。除了這個點以外，其它的點都被覆蓋了，所以只能向外連非匹配邊，而1號點可以向外連匹配邊
或非匹配邊。

如果1號點沒有被外面的點匹配，那么無論從其它的哪個點走進來，都能以1為終點找到增廣路。(要么順時針跑到1，要么逆時針)

同理如果1號點被外面的點匹配了，那么無論從其它的哪個點走進來，都能把這個圈看成一個點，然后從1的那條匹配邊穿出去。(要么順時針，要么逆時針)

?于是這個奇環就可以看成一個點，其主要特性由1號點體現(諸如和誰匹配了之流)。

這個合成點就叫做花。這個算法的思想就是不斷地把奇環合成點，直至找到增廣路（合成了某朵花以后就把整朵花當成一個點）。

考慮用BFS搜索增廣路。

圍觀wiki這個圖

?

由于BFS的性質，我們找到奇環只能是和同層的點，或者下下一層的點。

然后奇環的關鍵點必然是這棵BFS樹里深度最淺的點。然后考慮合成以后，花如何展開對應的路徑，使得我們能夠增廣。

花套花這個東西想起來都糾結>_<。

amber的程序里面并沒有把點真的合成，只是弄了一個表示集合的標號：Base，然后鄰接矩陣就不用變來變去了。

對于花中連向父親的是匹配邊的點，他的增廣路顯然是直接順著父親走，而如果連向父親的邊是非匹配邊的點，那么顯然是往后走然后跑過紅色的橫插邊，然后再向上跑回關鍵點。

注意到如果連向父子的邊是匹配邊的點原先是不需要Father這個域來描述的，直接用表示匹配的那個域就可以了。但是現在在花中，他的Father這個域就要起作用了，用來向后指向，然后繞過紅色橫插邊然后再跑回關鍵點。

實在是太精妙了。

1 //Problem:http://acm.timus.ru/problem.aspx?space=1&num=1099 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <iostream> 6 #include <algorithm> 7 using namespace std; 8 const int N=250; 9 int n; 10 int head; 11 int tail; 12 int Start; 13 int Finish; 14 int link[N]; //表示哪個點匹配了哪個點 15 int Father[N]; //這個就是增廣路的Father……但是用起來太精髓了 16 int Base[N]; //該點屬于哪朵花 17 int Q[N]; 18 bool mark[N]; 19 bool map[N][N]; 20 bool InBlossom[N]; 21 bool in_Queue[N]; 22 23 void CreateGraph(){ 24 int x,y; 25 scanf("%d",&n); 26 while (scanf("%d%d",&x,&y)!=EOF) 27 map[x][y]=map[y][x]=1; 28 } 29 30 void BlossomContract(int x,int y){ 31 fill(mark,mark+n+1,false); 32 fill(InBlossom,InBlossom+n+1,false); 33 #define pre Father[link[i]] 34 int lca,i; 35 for (i=x;i;i=pre) {i=Base[i]; mark[i]=true; } 36 for (i=y;i;i=pre) {i=Base[i]; if (mark[i]) {lca=i; break;} } //尋找lca之旅……一定要注意i=Base[i] 37 for (i=x;Base[i]!=lca;i=pre){ 38 if (Base[pre]!=lca) Father[pre]=link[i]; //對于BFS樹中的父邊是匹配邊的點，Father向后跳 39 InBlossom[Base[i]]=true; 40 InBlossom[Base[link[i]]]=true; 41 } 42 for (i=y;Base[i]!=lca;i=pre){ 43 if (Base[pre]!=lca) Father[pre]=link[i]; //同理 44 InBlossom[Base[i]]=true; 45 InBlossom[Base[link[i]]]=true; 46 } 47 #undef pre 48 if (Base[x]!=lca) Father[x]=y; //注意不能從lca這個奇環的關鍵點跳回來 49 if (Base[y]!=lca) Father[y]=x; 50 for (i=1;i<=n;i++) 51 if (InBlossom[Base[i]]){ 52 Base[i]=lca; 53 if (!in_Queue[i]){ 54 Q[++tail]=i; 55 in_Queue[i]=true; //要注意如果本來連向BFS樹中父結點的邊是非匹配邊的點，可能是沒有入隊的 56 } 57 } 58 } 59 60 void Change(){ 61 int x,y,z; 62 z=Finish; 63 while (z){ 64 y=Father[z]; 65 x=link[y]; 66 link[y]=z; 67 link[z]=y; 68 z=x; 69 } 70 } 71 72 void FindAugmentPath(){ 73 fill(Father,Father+n+1,0); 74 fill(in_Queue,in_Queue+n+1,false); 75 for (int i=1;i<=n;i++) Base[i]=i; 76 head=0; tail=1; 77 Q[1]=Start; 78 in_Queue[Start]=1; 79 while (head!=tail){ 80 int x=Q[++head]; 81 for (int y=1;y<=n;y++) 82 if (map[x][y] && Base[x]!=Base[y] && link[x]!=y) //無意義的邊 83 if ( Start==y || link[y] && Father[link[y]] ) //精髓地用Father表示該點是否 84 BlossomContract(x,y); 85 else if (!Father[y]){ 86 Father[y]=x; 87 if (link[y]){ 88 Q[++tail]=link[y]; 89 in_Queue[link[y]]=true; 90 } 91 else{ 92 Finish=y; 93 Change(); 94 return; 95 } 96 } 97 } 98 } 99 100 void Edmonds(){ 101 memset(link,0,sizeof(link)); 102 for (Start=1;Start<=n;Start++) 103 if (link[Start]==0) 104 FindAugmentPath(); 105 } 106 107 void output(){ 108 fill(mark,mark+n+1,false); 109 int cnt=0; 110 for (int i=1;i<=n;i++) 111 if (link[i]) cnt++; 112 printf("%d\n",cnt); 113 for (int i=1;i<=n;i++) 114 if (!mark[i] && link[i]){ 115 mark[i]=true; 116 mark[link[i]]=true; 117 printf("%d %d\n",i,link[i]); 118 } 119 } 120 121 int main(){ 122 // freopen("input.txt","r",stdin); 123 CreateGraph(); 124 Edmonds(); 125 output(); 126 return 0; 127 }

?

　　然后還有一篇，鏈接請猛戳。。

在北京冬令營的時候，yby提到了“帶花樹開花”算法來解非二分圖的最大匹配。

于是，我打算看看這是個什么玩意。其實之前，我已經對這個算法了解了個大概，但是。。。真的不敢去寫。 有一個叫Galil Zvi的人（應該叫計算機科學家），寫了篇論文： Efficient Algorithms for Finding Maximal Matching in Graphs （如果你在網上搜不到，可以：http://builtinclz.abcz8.com/art/2012/Galil%20Zvi.pdf） 這篇論文真神啊，它解決了4個問題： （一般圖+二分圖）的（最大匹配+最大權匹配）問題。 算法的思想、故事，請自己看論文吧。 這個論文告訴了我們很多有趣的東西，例如： 用Dinic實現的二分圖匹配的時間復雜度其實是O(M*N^0.5)，這也許能夠解釋為什么一般網絡流算法比Hungry要快了。 另外，帶花樹算法的正確性的證明比較困難；而其時間復雜度是可以做到O(M*N^0.5)的，不過要詳細實現，那么就快能到“ACM最長論文獎”了。 我寫了一個實例代碼：

http://builtinclz.abcz8.com/art/2012/ural1099.cpp

沒錯，這是用來解決URAL 1099 Work Schedule那題的。時間復雜度是O（N＾３）

簡述一下“帶花樹”算法吧： 它的核心思想還是找增廣路。假設已經匹配好了一堆點，我們從一個沒有匹配的節點s開始，使用BFS生成搜索樹。每當發現一個節點u，如果u還沒有被匹配，那么就可以進行一次成功的增廣；否則，我們就把節點u和它的配偶v一同接到樹上，之后把ｖ丟進隊列繼續搜索。我們給每個在搜索樹上的點一個類型：S或者T。當ｕ把它的配偶ｖ扔進隊列的時候，我們把ｕ標記為T型，ｖ標記為S型。于是，搜索樹的樣子是這樣的： ｓ ／　　＼ ａ　　　　ｂ ｜　　　　｜ ｃ　　　　ｄ ／　＼　　／　＼ ｅ　ｆ　　ｕ　ｊ ｜　｜　　｜　｜ ｉ　ｊ　　ｖ　ｋ 其中，黑色豎線相連的兩個點是已經匹配好的，藍色斜線表示兩個點之間有邊，但是沒有配對。T型的用紅色，S型的用黑色。 這里有個小問題：一個S型點ｄ在某一步擴展的時候發現了點ｕ，如果ｕ已經在搜索樹上了（即，出現了環），怎么辦？ 我們規定，如果ｕ的類型是T型，就無視這次發現；（這意味著我們找到了一個長度為偶數的環，直接無視） ｓ ／　　＼ ａ　　　　ｂ ｜　　　　｜ ｃ　　　　ｄ　　　如果連出來的邊是指向T型點的，就無視這個邊。 ／　＼　　／　＼ ｅ　ｆ＜－　　ｇ ｜　｜　　　　｜ ｉ　ｊ　　　　ｋ 否則，我們找到了一個長度為奇數的環，就要進行一次“縮花”的操作！所謂縮花操作，就是把這個環縮成一個點。 ｓ ／　　＼ ａ　　　　ｂ ｜　　　　｜ ｃ　　　　ｄ ／　＼　　／　＼ ｅ　ｆ　　｜　ｇ ｜　｜　　｜　｜ ｉ　ｕ＜－＋　ｋ 這個圖縮花之后變成了５個點（一個大點，或者叫一朵花，加原來的４個點）： 縮點完成之后，還要把原來環里面的T型點統統變成S型點，之后扔到隊列里去。 ＋－－－－－－－－－－－－－＋ ｜　　　　　　　　　　　　　｜ ｜　　　　　ｓ　　　　　　　｜ ｜　　　　／　　＼　　　　　｜ ｜　　　ａ　　　　ｂ　　　　｜ ｜　　　｜　　　　｜　　　　｜　　　現在是一個點了！還是一個S點。 ｜　　　ｃ　　　　ｄ　　　　｜ ｜　　／　＼　　／　＼　　　｜ ＋－｜－－　　ｆ－－ｕ　　－－－｜－－－＋ ｜　｜　　　　　　　　　　　　　｜　　　｜ ｜　｜　　　　　　　　｜　　　｜ ｜　｜　　　　　　　　　　　　　｜　　　｜ ｜　＋－－－－－－－－－－－－－＋　　　｜ ｜　　　　　　　　　　　　　　　　　　　｜ ｅ　　　　　　　　　　　　　　　　　　　ｇ ｜　　　　　　　　　　　　　　　　　　　｜ ｉ　　　　　　　　　　　　　　　　　　　ｋ 為什么能縮成一個點呢？我們看一個長度為奇數的環（例如上圖中的ｓ－ｂ－ｄ－ｊ－ｆ－ｃ－ａ－），如果我們能夠給它中的任意一個點找一個出度（配偶），那么環中的其他點正好可以配成對，這說明，每個點的出度都是等效的。例如，假設我們能夠給圖中的點ｄ另找一個配偶（例如ｄ＇好了），那么，環中的剩下６個點正好能配成３對，一個不多，一個不少（算上ｄ和ｄ＇一共４對剛剛好）。 ａ－ｓ－ｂ－ｄ－ｄ＇　　　　　　　　　ａ　ｓ－ｂ　ｄ－ｄ＇ ＼　　　　｜　　　　　　　＝＞　　　　＼　　　　　 ｃ－ｆ－ｕ　　　　　　　　　　　　　　ｃ　ｆ－ｕ 這就是我們縮點的思想來源。有一個勞苦功高的計算機科學家證明了：縮點之前和縮點之后的圖是否有增廣路的情況是相同的。 縮起來的點又叫一朵花（ｂｌｏｓｓｏｍ）． 注意到，組成一朵花的里面可能嵌套著更小的花。 當我們最終找到一條增廣路的時候，要把嵌套著的花層層展開，還原出原圖上的增廣路出來。 嗯，現在你對實現這個算法有任何想法嗎？ 天啊，還要縮點……寫死誰。。。。。。 我一開始也是這么想的。 我看了一眼網上某個大牛的程序，之后結合自己的想法，很努力地寫出了一個能AC的版本。 實現的要點有什么呢？ 首先，我們不“顯式”地表示花。我們記錄一個Nｅｘｔ數組，表示最終增廣的時候的路徑上的后繼。同時，我們維護一個并查集，表示每個點現在在以哪個點為根的花里（一個花被縮進另一朵花之后就不算花了）。還要記錄每個點的標記。 主程序是一段BFS。對于每個由ｘ發展出來的點ｙ，分４種情況討論： １。ｘｙ是配偶（不說夫妻，這是非二分圖。。。）或者ｘｙ現在是一個點（在一朵花里）：直接無視 ２。ｙ是T型點：直接無視 ３。ｙ目前單身：太好了，進行增廣！ ４。ｙ是一個S型點：縮點！縮點！ 縮點的時候要進行的工作： １。找ｘ和ｙ的LCA（的根）ｐ。找LCA可以用各種方法。。。直接樸素也行。 ２。在Nｅｘｔ數組中把ｘ和ｙ接起來（表示它們形成環了！） ３。從ｘ、ｙ分別走到ｐ，修改并查集使得它們都變成一家人，同時沿路把Nｅｘｔ數組接起來。 Nｅｘｔ數組很奇妙。每時每刻，它實際形成了若干個掛在一起的雙向鏈表來表示一朵花內部的走法。 －－－－ ／　　　　＼＜－－＋ ｜　　　　｜　　　｜ ｜　　　　｜＜－－＋ ｖ　　　　ｖ －－－－－－－－－－ ／　　　　　　　　　　＼ ＋－　　　　　　　　　　　　－－＋ ｜　　　　　　　　　　　　　　　｜ ｜　　　　　　　　　　　　　　　｜ ＋－－－－＞ｓ　　＜－－－－－－＋　　　　　 有權圖的最大匹配怎么做？ 看論文吧。。。用類似KM的方法，不過，是給每個花再來一個權值。真的很復雜。。。 有一個人寫了代碼，好像是GPL許可證。。。你最好想辦法搜到它的網站來看看版權的問題；總之，我先貼出來： http://builtinclz.abcz8.com/art/2012/mwmatching.py

轉載于:https://www.cnblogs.com/zhsl/p/3271754.html

總結

以上是生活随笔為你收集整理的[转]带花树,Edmonds's matching algorithm,一般图最大匹配的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。