所謂花，就是如下圖所示的一個奇環：

本文中粗邊代表現在的匹配邊，細邊代表該點的前驅（后文會講解前驅是什么，現在只需要知道每個點和它的前驅在原圖中一定是有邊的）。

如圖所示，一朵包含\(2k+1\)個點的花一定至多包含\(k\)條匹配邊，于是總會剩下一個未匹配的點，上圖中即為\(1\)號點。

那么我們可以發現，如果有另外一個點想要與花中的某個點\(v\)匹配，那么有兩種情況：1、\(v\)是未匹配的點（即1號點），那么直接與\(v\)匹配即可。2、\(v\)是已經匹配的點，這時只要將花中的匹配狀況修改，使得\(v\)變成未匹配的那個點即可。

綜上所述，只要花中的點沒有向外匹配，我們總是可以使得外部的一個點和花中任意一個點匹配，因此花的性質和點其實很相似。我們將花縮成一個點來處理，就可以解決出現奇環的問題。以上思想就是帶花樹算法的核心。

==================總之分割一下好了==================

帶花樹算法的過程其實和\(bfs\)版本的匈牙利是很相似的，都是找出一個交錯樹，交錯樹可能長這樣（注意每個藍色點可能有多個橙色兒子，但是每個橙色點只能有一個藍色兒子）：

其中1號點就是我們嘗試增廣的節點，在這里我們給每一個節點一個\(type\)值，若該點不在交錯樹中，它的\(type\)值為\(0\)，否則為\(1\)或\(2\)。上圖中我們用藍色點代表\(type=1\)的點，橙色點代表\(type=2\)的點，不難看出\(type\)值的不同其實代表了一種類似于二分圖的關系，每個點在交錯樹中只和\(type\)值不同的點相連。當我們沒有找到奇環的時候，\(type\)值和二分圖是等價的。

那么仿照匈牙利的過程，我們將嘗試增廣的點\(v\)的\(type\)值設為\(1\)并開始增廣，假設當前處理的點為\(u\)：

1、如果\(type_u=0\)，就代表它不在交錯樹中：

當\(u\)已經有匹配時，我們就擴展這棵交錯樹，將\(type_u\)的值設為\(2\)（因為其和\(type\)值為\(1\)的\(v\)相鄰），并將\(type_{match_u}\)的值設為\(1\)（同理）。這時我們就可以把\(match_u\)塞進隊列里了，如果能夠沿著\(match_u\)找到增廣路的話我們就可以讓\(match_u\)匹配那個增廣的點并將\(u\)與\(v\)匹配，這樣就使匹配數增加了\(1\)。同時我們將\(u\)的前驅（用\(pre_u\)表示）設置為\(v\)，這是為了方便在找到增廣路以后一路返回修改匹配。

當\(u\)并沒有匹配時，我們就成功找到了一條增廣路，此時沿著由\(pre\)和\(match\)連成的邊一路修改就增廣完成了，返回。

2、如果\(type_u=2\)，代表你找到了一個偶環，并沒有什么用，就跳過這個點。

3、這里是最重點的，如果\(type_u=1\)，代表你找到了一個奇環，這就代表你的\(type\)值不再等價于二分圖了，我們這個時候就可以開始“縮花”操作，將我們找到的奇環縮成一個點。讓我們具體的考慮一下：

首先，快速找到哪些點在這個奇環中，顯然\(u\)和\(v\)一定都出現在交錯樹上（\(type\)不為\(0\)），結合上面的那張圖考慮，奇環的范圍就是兩個點在交錯樹上的鏈中包含的所有點，因此我們需要找到這兩個點的\(lca\)，這里直接采用暴力向上跳的做法即可。

找到以后怎么連接\(pre\)邊呢？我們參考一下文章開頭的結構，可以發現此時的\(lca\)一定就是那個花中唯一的沒有匹配或者匹配到外面節點的\(1\)號點。因此感性思考一下，我們應該“誘導”其他所有的點通過\(pre\)和\(match\)邊一路走走到\(lca\)上，因此將除了與\(lca\)相連的\(pre\)邊外其他的\(pre\)邊都改為雙向邊，并將\(u\)和\(v\)也改成雙向邊即可達到這個目的。

最后做一點掃尾工作，我們可以通過并查集將奇環縮成一個點（因此在普通增廣的時候也要考慮并查集的情況），不妨用\(lca\)做這朵花的代表。同時再考慮一下這個新點的\(type\)值應該設為什么，因為每個橙色點最多只有一個兒子（它的匹配點），因此\(lca\)一定是藍色點，因此新點的\(type\)值為\(1\)，所以要注意將花中所有\(type\)值為\(2\)的點修改為\(1\)并且加入隊列。

當我們找不到新的點時，本次增廣失敗。

===============分割分割================

以上就是一般圖最大匹配的增廣過程，注意在每次增廣之前，\(pre\)，\(type\)以及并查集都是要初始化的。將并查集的復雜度看作常數，則每次增廣至多是\(O(m)\)的，一共需要增廣\(O(n)\)次，因此帶花樹算法的復雜度和匈牙利一樣，都是\(O(nm)\)，當然，在實踐中帶花樹算法跑得一般會比理論上界快很多。

相信在熟練理解帶花樹的過程后一定能寫出代碼，因此為了不對讀者造成思維定式影響這里就不貼代碼了。完結撒花~

轉載于:https://www.cnblogs.com/Mr-Spade/p/9636874.html

總結

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

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