Matching

一張無向圖，相鄰兩點配成一對。但是呢——一個點最多只能與一個鄰點配成一對，寧可孤家寡人，不可三妻四妾。雙雙對對的邊，整體形成一個「匹配」。

換句話說：挑選一些邊，讓圖上每一點僅接觸零條邊或一條邊。這些邊構成的集合，稱作一個「匹配」。

Matched Vertex與Unmatched Vertex

一個點要嘛跟另一個點比翼雙飛，要嘛孑然一身──前者為「匹配點」，後者為「未匹配點」。

Matched Edge與Unmatched Edge

出雙入對的兩點之間的邊為「匹配邊」，除此以外則為「未匹配邊」。一個匹配由許多匹配邊組成。

Cardinality

一個匹配擁有的匹配邊數目，稱作「基數」。

「基數」源自集合論，意義是集合的大小。

順便介紹一些特別的匹配：

maximal matching
一張圖中，沒有辦法直接增加配對數的匹配。

maximum matching
一張圖中，配對數最多的匹配。也是maximal matching。

perfect matching
一張圖中，所有點都送作堆的匹配。也是maximum matching。

Weight

當圖上的邊都有權重，一個匹配的權重是所有匹配邊的權重總和。

順便介紹一些特別的匹配：

maximum weight matching
一張圖中，權重最大的匹配。

maximum weight maximum (cardinality) matching
一張圖中，配對數最多的前提下，權重最大的匹配。

maximum weight perfect matching
一張圖中，所有點都送作堆的前提下，權重最大的匹配。

Bipartite Graph

「二分圖」是圖的一種特例。一張二分圖的結構是：兩群點（通常標記作X集合與Y集合）、橫跨這兩群點的邊（X與Y之間）。至於兩群點各自之內是沒有邊的（X與X、Y與Y間）。

順帶一提，二分圖構造較單純，其資料結構可以進行精簡：

Bipartite Matching

一張二分圖上的匹配，稱作「二分匹配」。所有的匹配邊，都是這橫跨這兩群點的邊，就像是連連看。

使用Flow尋找Bipartite Matching

一側接上源點，一側接上匯點，即可利用網路流來解決最大二分匹配問題、最大（小）權二分匹配問題。

導讀

Augmenting Path Theorem是尋找最大匹配的重要理論。本章節當中，首先介紹相關元件，然後證明理論，最後提出一種尋找最大匹配的手段。

Alternating Path與Alternating Cycle

「交錯路徑」與「交錯環」。在一張存在匹配的圖上，匹配邊和未匹配邊彼此相間的一條路徑與一個環。

交錯環有個有趣的特性：顛倒交錯環上的匹配邊和未匹配邊，可以改變匹配，但是不影響Cardinality。

Augmenting Path

「擴充路徑」。一條交錯路徑，第一個點和最後一個點都是未匹配點。因此第一條邊和最後一條邊都是未匹配邊。

擴充路徑有個更有趣的特性：顛倒擴充路徑上的匹配邊和未匹配邊，可以改變匹配，並且讓Cardinality加一。

Symmetric Difference

兩個集合A和B的「對稱差集」定義為A⊕B = (A∪B) - (A∩B)。例如A = {1,3,4,5}、B = {2,4,5,7}、A⊕B = {1,2,3,7}，沒有重複出現的元素將會留下，重複出現的元素將會消失。

對稱差集非常適合用來描述「顛倒擴充路徑上的匹配邊與未匹配邊」這件事情。現在有一個匹配M，和一條擴充路徑P（拆開成邊），那麼M⊕P會等於新匹配。

坊間書籍常以對稱差集來表述匹配相關理論。在此特別將對稱差集的概念介紹給各位，希望各位往後遇到⊕這個符號時，不會下意識地認為它艱深晦澀。

Symmetric Difference of Matchings

同一張圖上的兩種匹配M和M*也可以計算對稱差集M⊕M*，總共會產生六大類connected component，都是交錯路徑或者交錯環，各位若是不信可以親自實驗看看：

兩個匹配的對稱差集，提供了這兩個匹配互相變換的管道：對其中一個匹配來說，只要顛倒整個對稱差集當中的匹配邊與未匹配邊，就變成另一個匹配。寫成數學式子就是：令M⊕M* = P，則M⊕P = M*、M*⊕P = M。

Augmenting Path Theorem

從圖上任取一個未匹配點，如果找不到以此點作為端點的擴充路徑，那麼這張圖會有一些最大匹配不會包含此點。

更進一步來說，就算從這張圖上刪除此點（以及相連的邊），以剩餘的點和邊，還是可以找到原本那張圖的其中一些最大匹配。

證明不困難，利用一下先前所學到的東西，便可以推理出來：

令當下的匹配M找不到以未匹配點p作為端點的擴充路徑。
令M*是該圖的其中一個最大匹配。
一、如果p不在M*上：
　　刪除此點完全不會對M和M*有任何影響，定理成立。
二、如果p在M*上：
　甲、p對於M來說是未匹配點。理所當然p不在M上。
　乙、考慮M⊕M*的六種情形。p不在M上，且p在M*上，所以只有d或e符合條件。
　丙、M找不到以p作為端點的擴充路徑，所以d不符合條件，只有e符合條件。
　丁、對於M*來說，只要照著e顛倒匹配邊和未匹配邊，
　　　就可以製造出另一個不會包含p的最大匹配，
　　　成為步驟一的情況，定理還是成立。

這個理論相當重要，它表明了一個找最大匹配的手段：

遞歸法，不斷刪除找不到擴充路徑的未匹配點，減小問題規模，減小圖的規模。無論刪除多少點，依然能保留原圖的某些最大匹配。

一、一開始圖上所有點都是未匹配點。
二、每個未匹配點，依序嘗試作為擴充路徑的端點：
　甲、如果找得到擴充路徑：
　　　沿著擴充路徑修改現有匹配，以增加Cardinality。
　　　（此未匹配點變成了匹配點。）
　乙、如果找不到擴充路徑：
　　　直接刪除此點。繼續下去仍然可以找到原圖的其中一個最大匹配。
　　　（此未匹配點被刪除。）

所有的未匹配點，要嘛變成匹配點、要嘛被刪除。未匹配點盡數消失，同時產生其中一個最大匹配。

Augmenting Path Theorem另一種形式

一個匹配，若無擴充路徑，即是最大匹配。

要是圖上所有未匹配點都不能當作擴充路徑的端點，就代表著圖上根本就沒有擴充路徑。Cardinality無法增加，就代表著當下的匹配就是最大匹配囉！

這個理論相當重要，它表明了一個找最大匹配的手段：

不斷找擴充路徑，直到找不到為止。此時的匹配就是最大匹配。

導讀

以下章節將介紹Matching的各種演算法。每當講解一個演算法，先談比較簡單的特例Bipartite Matching，再談比較複雜的通例Matching，循序漸進講解。

用途

找出一張二分圖的其中一個最大二分匹配。

Alternating Tree

選定一個未匹配點作為起點，嘗試列出所有的交錯路徑──藉此尋找擴充路徑。

有個重要的發現：當兩條交錯路徑撞在同一個點，將來還是只能選擇其中一條路徑來進行擴充，所以只要留下一條路徑就夠了。

根據這個重要的發現，圖上的每個點、每條邊只需出現一次。我們得以使用Graph Traversal來尋找一條擴充路徑，並形成一棵樹，稱作「交錯樹」。

二分圖當中，每條交錯路徑都在X與Y之間來回。

演算法

一、一開始圖上所有點都是未匹配點。
二、X的每個未匹配點，依序嘗試作為擴充路徑的端點。
　　以Graph Traversal建立交錯樹，以尋找擴充路徑。
　　（X的未匹配點一旦處理完畢，Y的未匹配點不會再有擴充路徑，故只需找X側。）
　甲、如果找得到擴充路徑：
　　　沿著擴充路徑修改現有匹配，以增加Cardinality。
　　　（此未匹配點變成了匹配點。）
　乙、如果找不到擴充路徑：
　　　直接刪除此點。繼續下去仍然可以找到原圖的其中一個最大匹配。
　　　（此未匹配點被刪除。）

這個演算法運作起來，如同接上了源點與匯點再進行Ford–Fulkerson Algorithm（Augmenting Path Algorithm）。

時間複雜度

時間複雜度是O(V)次Graph Traversal的時間。圖的資料結構為Adjacency Matrix是O(V³)；圖的資料結構為Adjacency Lists是O(VE)。

找出一個最大二分匹配

以DFS尋找擴充路徑，程式碼變得相當精簡。

採用BFS也是可以的，這裡就不贅述了。

const int X = 100; // X的點數 const int Y = 100; // Y的點數 int mx[X], my[Y]; // X各點的配對對象、Y各點的配對對象 bool vy[Y]; // 記錄Graph Traversal拜訪過的點 bool adj[X][Y]; // 精簡過的adjacency matrix // 以DFS建立一棵交錯樹 bool DFS(int x) { for (int y=0; y<Y; ++y) if (adj[x][y] && !vy[y]) { vy[y] = true; // 找到擴充路徑 if (my[y] == -1 || DFS(my[y])) { mx[x] = y; my[y] = x; return true; } } return false; } int bipartite_matching() { // 全部的點初始化為未匹配點。 memset(mx, -1, sizeof(mx)); memset(my, -1, sizeof(my)); // 依序把X中的每一個點作為擴充路徑的端點， // 並嘗試尋找擴充路徑。 int c = 0; for (int x=0; x<X; ++x) // if (mx[x] == -1) // x為未匹配點，這行可精簡。 { // 開始Graph Traversal memset(vy, false, sizeof(vy)); if (DFS(x)) c++; } return c; }

Greedy Matching

這裡介紹一個加速手段：明顯可以配對的點，預先配對。如此一來這些點就不必建立交錯樹。圖很龐大的時候，得以發揮功效。

雖然多了一次Graph Traversal，但是少了許多棵交錯樹。

int greedy_matching() { int c = 0; for (int x=0; x<X; ++x) if (mx[x] == -1) for (int y=0; y<Y; ++y) if (my[y] == -1) if (adj[x][y]) { mx[x] = y; my[y] = x; c++; break; } return c; } int bipartite_matching() { memset(mx, -1, sizeof(mx)); memset(my, -1, sizeof(my)); int c = greedy_matching(); // 能連的先連一連 for (int x=0; x<X; ++x) if (mx[x] == -1) // 這行記得補上來 { memset(vy, false, sizeof(vy)); if (DFS(x)) c++; } return c; }

UVa 259 670 753 10080 10092 10243 10418 10984 663 11148

用途

找出一張無向圖的其中一個最大匹配。

Alternating Tree: Cross Edge

交錯樹當中，「偶點」距離樹根偶數條邊，「奇點」距離樹根奇數條邊。一般圖的交錯樹、二分圖的交錯樹，兩者有個不同之處──偶點到偶點的邊。

二分圖的交錯樹
偶點到奇點：一定是未匹配邊。
奇點到偶點：一定是已匹配邊。
偶點到偶點：二分圖不會有這種邊。
奇點到奇點：二分圖不會有這種邊。

一般圖的交錯樹
偶點到奇點：一定是未匹配邊。
奇點到偶點：一定是已匹配邊。
偶點到偶點：一定是未匹配邊，且會形成「花」。
奇點到奇點：交錯樹不會有這種邊，因為不會形成交錯路徑。

Alternating Tree: Cycle

偶點到偶點的邊，在交錯樹上形成一個環。只要穿越這條偶點到偶點的邊，以繞遠路的方式，環上所有奇點都能夠成為偶點，而且延伸出更多條交錯路徑。

一般圖的交錯樹，多了偶點到偶點的邊，奇點因此活躍了。環上的所有奇點，可以搖身一變成為偶點，然後重新延伸出交錯路徑！

Blossom與Base

在交錯樹上，分岔的兩段交錯路徑，接上一條偶點到偶點的邊，所形成的奇數條邊的環，就稱作「花」。花上兩條未匹配邊的銜接點，則稱作「花托」，宛如花開在交錯樹上。

Blossom Contraction

既然花上的點都可以成為偶點，那麼乾脆把花直接縮成一個偶點，讓交錯樹更簡潔明白。

交錯樹上可能會有許多偶點到偶點的邊，形成許多朵重重疊疊的花，我們可以用任意順序縮花。實作時，為了容易找到花，可以在建立交錯樹的途中，一旦發現偶點到偶點的邊就立即縮花。一句話，一旦發現花就立即縮花。

縮花的次數呢？一朵花最少有三個點，縮花後成為一個點，前前後後少了兩個點。由此推得：V個點的圖建立一棵交錯樹，最多縮花V/2次；如果再多縮幾朵花，樹上就沒有點了。

路徑沿著花繞來繞去，繞得你暈頭轉向。

演算法

一、一開始圖上所有點都是未匹配點。
二、每個未匹配點，依序嘗試作為擴充路徑的端點，
　　並以Graph Traversal建立交錯樹，以尋找擴充路徑。
　甲、走到未拜訪過的點：
　　a. 如果是已匹配點，則延伸交錯樹，一條未匹配邊再加一條已匹配邊。
　　b. 如果是未匹配點，則找到擴充路徑。
　乙、走到已拜訪過的點：
　　a. 如果是偶點，形成花。做花的處理。
　　b. 如果是奇點，根據只需留一條路徑的性質，什麼都不必做。

花的處理：
一、找出花托：cross edge兩端點的Lowest Common Ancestor。
二、建立從樹根到花上各奇點之交錯路徑。
　　一定會經過cross edge。小心別重複經過花托。
三、把花上面的點全部當作偶點。
　　或者，乾脆把花直接縮成一個偶點。
　　縮花可用Disjoint Sets資料結構。

找出一個最大匹配

採用BFS建立交錯樹。採用Array記錄交錯路徑，以大量Array紀錄交錯樹上每一條交錯路徑。不縮花。

一、V個未匹配點分別建立交錯樹。二、一棵交錯樹最多V條交錯路徑，一條交錯路徑長度最多V條邊。三、一棵交錯樹最多E朵花，每朵花需要O(V)時間找花托。

時間複雜度O(V³ + V²E)，通常簡單寫成O(V²E)。

const int V = 50; // 圖的點數 bool adj[V][V]; // adjacency matrix deque<int> p[V]; // p[x]記錄了樹根到x點的交錯路徑。 int m[V]; // 記錄各點所配對的點，值為-1為未匹配點。 int d[V]; // 值為-1未拜訪、0偶點、1奇點。 int q[V], *qf, *qb; // queue，只塞入偶點。 // 設定好由樹根至花上各個奇點的交錯路徑，並讓奇點變成偶點。 // 只處理花的其中一邊。 // 邊xy是cross edge。b是花托。 void label_one_side(int x, int y, int b) { for (int i=b+1; i<p[x].size(); ++i) { int z = p[x][i]; if (d[z] == 1) { // 設定好由樹根至花上奇點的交錯路徑。 // 會經過cross edge。 p[z] = p[y]; p[z].insert(p[z].end(), p[x].rbegin(), p[x].rend()-i); d[z] = 0; // 花上的奇點變偶點 *qb++ = z; // 將來可以延伸出交錯路徑 } } } // 給定一個未匹配點r，建立交錯樹。 bool BFS(int r) { for (int i=0; i<V; ++i) p[i].clear(); p[r].push_back(r); // 交錯樹樹根 memset(d, -1, sizeof(d)); d[r] = 0; // 樹根是偶點 qf = qb = q; *qb++ = r; // 樹根塞入queue while (qf < qb) for (int x=*qf++, y=0; y<V; ++y) if (adj[x][y] && m[y] != y) // 有鄰點，點存在。 if (d[y] == -1) // 沒遇過的點 if (m[y] == -1) // 發現擴充路徑 { for (int i=0; i+1<p[x].size(); i+=2) { m[p[x][i]] = p[x][i+1]; m[p[x][i+1]] = p[x][i]; } m[x] = y; m[y] = x; return true; } else // 延伸交錯樹 { int z = m[y]; p[z] = p[x]; p[z].push_back(y); p[z].push_back(z); d[y] = 1; d[z] = 0; *qb++ = z; } else if (d[y] == 0) // 形成花 { // 從兩條交錯路徑當中尋找花托 int b = 0; while (b < p[x].size() && b < p[y].size() && p[x][b] == p[y][b]) b++; b--; // 兩條路徑分頭處理 label_one_side(x, y, b); label_one_side(y, x, b); } else // 只需留一條路徑 ; return false; } int matching() { memset(m, -1, sizeof(m)); int c = 0; for (int i=0; i<V; ++i) if (m[i] == -1) if (BFS(i)) c++; // 找到擴充路徑，增加匹配數 else m[i] = i; // 從圖上刪除此點 return c; } void demo() { cout << "匹配數為" << matching(); for (int i=0; i<V; ++i) // 印出所有的匹配邊 if (i < m[i]) cout << i << ' ' << m[i] << endl; }

找出一個最大匹配

採用BFS建立交錯樹，以Disjoint-sets Forest實作縮花。縮花時，將花托設定為Disjoint-sets Forest的樹根，程式碼比較簡潔。

一棵交錯樹的建立過程當中，縮花縮掉的點不會再度出現。導致尋找花托、也就是LCA的總時間複雜度從O(VE)降為O(V+E)。也導致merge與find的總時間複雜度從O(Eα(V))降為O(V+E)。

時間複雜度是V次Graph Traversal的時間。圖的資料結構為Adjacency Matrix是O(V³)；圖的資料結構為Adjacency Lists是O(VE)。

順帶一提，也可以一口氣把圖上所有未匹配點作為樹根，建立交錯森林。當兩棵交錯樹碰到的時候，就是有擴充路徑了。這麼做可以稍微降低縮花的次數。

const int V = 50; // 圖的點數 bool adj[V][V]; // adjacency matrix int p[V]; // 交錯樹 int m[V]; // 記錄各點所配對的點，值為-1為未匹配點。 int d[V]; // 值為-1未拜訪、0偶點、1奇點。 int c1[V], c2[V]; // 記錄花上各奇點所經過的cross edge int q[V], *qf, *qb; // queue，只塞入偶點。 /* disjoint-sets forest */ int pp[V]; int find(int x) {return x == pp[x] ? x : (pp[x] = find(pp[x]));} // void merge(int x, int y) {pp[find(x)] = find(y);} void merge(int x, int y) {pp[x] = y;} /* lowest common ancestor */ int v[V]; // 繞一繞花，找出擴充路徑，並擴充。源頭是r，末梢是x。 // 最初以偶點作為末端，每次往回走一條匹配邊加一條未匹配邊， // 如果遇到花上奇點，就要繞花，以cross edge拆成兩段路徑。 void path(int r, int x) { if (r == x) return; if (d[x] == 0) // 還是偶點，繼續往回走。 { path(r, p[p[x]]); int i = p[x], j = p[p[x]]; m[i] = j; m[j] = i; } else if (d[x] == 1) // 遇到花上奇點，就要繞花。 { // 往回走會經過cross edge c1[x]-c2[x] path(m[x], c1[x]); // 頭尾要顛倒 path(r, c2[x]); int i = c1[x], j = c2[x]; m[i] = j; m[j] = i; } } // 邊xy是cross edge，同時一起往上找LCA。 // 時間複雜度O(max(x⤳b, y⤳b))，縮掉的點不會再遇到。 int lca(int x, int y, int r) { int i = find(x), j = find(y); while (i != j && v[i] != 2 && v[j] != 1) { v[i] = 1; v[j] = 2; if (i != r) i = find(p[i]); if (j != r) j = find(p[j]); } int b = i, z = j; if (v[j] == 1) swap(b, z); for (i = b; i != z; i = find(p[i])) v[i] = -1; v[z] = -1; return b; } /* // 一次就要O(V)的LCA演算法 int lca(int x, int y, int r) { int v[V] = {0}; v[r] = 1; for (x = find(x); x != r; x = find(p[x])) v[x] = 1; for (y = find(y); !v[y]; y = find(p[y])) ; return y; } */ // 設定好由樹根至花上各個奇點的交錯路徑，並讓奇點變成偶點。 // 只處理花的其中一邊。 // 邊xy是cross edge。b是花托。 void contract_one_side(int x, int y, int b) { for (int i = find(x); i != b; i = find(p[i])) { merge(i, b); // 縮花，花托成為DSF的樹根。 if (d[i] == 1) c1[i] = x, c2[i] = y, *qb++ = i; } } // 給定一個未匹配點r，建立交錯樹。 bool BFS(int r) { for (int i=0; i<V; ++i) pp[i] = i; // DSF初始化 memset(v, -1, sizeof(v)); // LCA初始化 memset(d, -1, sizeof(d)); d[r] = 0; // 樹根是偶點 qf = qb = q; *qb++ = r; // 樹根塞入queue while (qf < qb) for (int x=*qf++, y=0; y<V; ++y) // 有鄰點。點存在。縮花成同一點後則不必處理。 if (adj[x][y] && m[y] != y && find(x) != find(y)) if (d[y] == -1) // 沒遇過的點 if (m[y] == -1) // 發現擴充路徑 { path(r, x); m[x] = y; m[y] = x; return true; } else // 延伸交錯樹 { p[y] = x; p[m[y]] = y; d[y] = 1; d[m[y]] = 0; *qb++ = m[y]; } else if (d[find(y)] == 0) // 形成花 { int b = lca(x, y, r); contract_one_side(x, y, b); contract_one_side(y, x, b); } else // 只需留一條路徑 ; return false; }

Greedy Matching

先前章節提到的加速手段，此處也適用。

UVa 11439

用途

找出一張二分圖的其中一個最大二分匹配。

演算法

每回合一口氣找出所有的最短擴充路徑們，並且進行擴充，直到找不到為止。最多需要2sqrtV回合。證明請參考CLRS。

一、一開始圖上所有點都是未匹配點。
二、重複下列動作，直到找不到擴充路徑為止：
　　（最多需要2sqrtV回合。）
　甲、X的所有未匹配點同時作為樹根，
　　　採用BFS建立交錯森林，一層一層延展，
　　　直到發現所有的最短擴充路徑們。
　　　（時間複雜度是一次Graph Traversal的時間。）
　乙、各個樹根依序往樹葉方向尋找最短擴充路徑。
　　　也可以由樹葉往樹根找。
　　　一旦拜訪過的點就不再拜訪。
　　　（時間複雜度是一次Graph Traversal的時間。）

這個演算法運作起來，如同接上了源點與匯點再進行Blocking Flow Algorithm。

時間複雜度

時間複雜度是2sqrtV次BFS的時間。圖的資料結構為Adjacency Matrix是O(V²sqrtV) = O(V^2.5)；圖的資料結構為Adjacency Lists是O((V+E)sqrtV)，通常簡單寫成O(EsqrtV)。

找出一個最大二分匹配

const int X = 100; // X的點數 const int Y = 100; // Y的點數 int mx[X], my[Y]; // X各點的配對對象、Y各點的配對對象 int px[X], py[Y]; // 交錯森林 bool adj[X][Y]; // 精簡過的adjacency matrix // 由樹葉往樹根找擴充路徑，並擴充。 int trace(int y) { int x = py[y], yy = px[x]; py[y] = px[x] = -1; // 一旦拜訪過的點就不再拜訪 if (mx[x] == -1 || (yy != -1 && trace(yy))) { mx[x] = y; my[y] = x; return 1; } return 0; } int bipartite_matching() { memset(mx, -1, sizeof(mx)); memset(my, -1, sizeof(my)); int q[X], *qf, *qb; int c = 0; while (true) // 如果還能找到擴充路徑就繼續 { memset(px, -1, sizeof(px)); memset(py, -1, sizeof(py)); qf = qb = q; // 把X的未匹配點，作為交錯森林的樹根。 for (int x=0; x<X; ++x) if (mx[x] == -1) *qb++ = x; // 採用BFS建立交錯森林，一次僅延展一整層， // 直到發現所有目前最短的擴充路徑。 bool ap = false; // 是否存在擴充路徑 for (int* tqb = qb; qf < tqb && !ap; tqb = qb) for (int x=*qf++, y=0; y<Y; ++y) if (adj[x][y] /*&& mx[x] != y*/ && py[y] == -1) { py[y] = x; if (my[y] == -1) ap = true; else *qb++ = my[y], px[my[y]] = y; } if (!ap) break; // 由樹葉往樹根找擴充路徑，並擴充。 for (int y=0; y<Y; ++y) if (my[y] == -1 && py[y] != -1) c += trace(y); } return c; }

用途

找出一張無向圖的其中一個最大匹配。

演算法

每回合一口氣找出所有的最短擴充路徑們，並且進行擴充，直到找不到為止。

時間複雜度

O(EsqrtV)。

用途

求出一張二分圖的其中一個最大權完美二分匹配。稍做修改，也能求出最大權最大二分匹配、最大權二分匹配，以及最小權版本。

maximum weight bipartite matching
一張二分圖中，權重最大的二分匹配。

maximum weight maximum (cardinality) bipartite matching
一張二分圖中，配對數最多的前提下，權重最大的二分匹配。

maximum weight perfect bipartite matching
一張二分圖中，所有點都送作堆的前提下，權重最大的二分匹配。

調整權重

一個點連接的所有邊，等量增加權重、等量減少權重，都不會影響最大權完美匹配的位置。

此性質二分圖和一般圖都成立。

建立vertex labeling

幫各個點都創造一個變數，直接在點上調整權重，代替在邊上調整權重，藉此減少調整權重的時間。

最小化所有點的權重總和 = 最大化所有匹配邊的權重總和

建立一組vertex labeling：令圖上每一條邊，其兩端點的權重總和，大於等於邊的權重。

l(x) + l(y) ≥ adj(x,y)

所有點的權重總和，大於等於任意匹配的權重（所有匹配邊的權重總和）。

∑ l(x) ≥ ∑ adj(x,y)
V        M

盡力降低所有點的權重總和，就能逼近最大權完美匹配的權重。

min ∑ l(x) = max ∑ adj(x,y)
    V            M

求出一組總和最小的vertex labeling，就能得到最大權完美匹配。

求最大值變成了求最小值，這是很實用的數學轉換。這個轉換有個重要目的：操作vertex labeling而不操作edge labeling，藉此減少調整權重的時間。

【註：以Linear Programming的觀點來看，這個轉換正是primal problem與dual problem之間的轉換。】

Equality Edge（Admissible Edge）

「等邊」。兩端點的點權重相加，恰好等於邊權重。

l(x) + l(y) = adj(x,y)

當vertex labeling的總和降低到極限，可以發現最大權完美匹配的所有匹配邊都是等邊。

Augmenting Path Algorithm + Equality Edge

結合擴充路徑與等邊，得到最大權完美匹配演算法。

一、一開始圖上所有點都是未匹配點。
二、每個未匹配點，依序嘗試作為擴充路徑的端點。擴充路徑必須全是「等邊」。
　　以Graph Traversal建立交錯樹。交錯樹必須全是「等邊」。
　甲、如果找得到「等邊」擴充路徑：進行擴充。
　乙、如果找不到「等邊」擴充路徑：？？？？？

擴充路徑全是等邊，最後得到的最大權匹配當然全是等邊。

當找不到等邊，只好想辦法調整vertex labeling了。

調整vertex labeling

必須維持每一條邊的大於等於性質，而且既有等邊不能動。該如何調整權重呢？

先把等邊交錯樹延伸到極限，再窮舉末梢的非等邊，計算「兩端點的點權重相加、再減掉邊權重」，找到此差值最小者。

d = min { l(x) + l(y) - adj(x,y) }     x為樹上一點、y為樹外一點

樹上偶點減此值、樹上奇點加此值。一加一減，樹內樹外既有等邊保持不動，樹梢則有一條（以上）非等邊變成了等邊。

l(x) -= d     x為樹上偶點
l(x) += d     x為樹上奇點

如此便製造了一條（以上）的等邊，而且既有等邊保持不動，而且維持了每一條邊的大於等於性質。整張圖的等邊只增不減。

【註：這宛如最短路徑問題的調整權重手法。】

等邊交錯樹宛如最小生成樹，製造等邊宛如Prim's Algorithm，屢次找不在樹上、讓匹配權重下降最少的等邊。

演算法

一、建立vertex labeling，使之滿足前述的大於等於性質。
二、一開始圖上所有點都是未匹配點。
三、X的每個未匹配點，依序嘗試作為等邊擴充路徑的端點。
　　以Graph Traversal建立等邊交錯樹。
　　（X的未匹配點一旦處理完畢，Y的未匹配點不會再有擴充路徑，故只需找X側。）
　甲、如果找得到等邊擴充路徑：
　　　沿著等邊擴充路徑修改現有匹配，以增加Cardinality。
　乙、如果找不到等邊擴充路徑，則製造新等邊：
　　　等邊交錯樹末梢的非等邊，算最小差值d。（有人稱作slack）
　　　樹上偶點減d，樹上奇點加d。樹梢新增了一條以上的等邊。

找出一個最大權完美二分匹配

一、V個未匹配點分別建立交錯樹。二、一棵交錯樹最多V點，每次調整權重得以新增一點（以上）。三、每次調整權重之前，需要找到最小差值，最多窮舉E條邊。

時間複雜度是三者相乘。圖的資料結構為Adjacency Matrix是O(V⁴)；圖的資料結構為Adjacency Lists是O(VVE)。

const int X = 50; // X的點數，等於Y的點數 const int Y = 50; // Y的點數 int adj[X][Y]; // 精簡過的adjacency matrix int lx[X], ly[Y]; // vertex labeling int mx[X], my[Y]; // X各點的配對對象、Y各點的配對對象 bool vx[X], vy[Y]; // 記錄是否拜訪過 // 以DFS建立一棵等邊交錯樹 bool DFS(int x) { vx[x] = true; for (int y=0; y<Y; ++y) if (!vy[y]) // 遇到等邊，延展交錯樹。 if (lx[x] + ly[y] == adj[x][y]) { vy[y] = true; if (my[y] == -1 || DFS(my[y])) { mx[x] = y; my[y] = x; return true; } } return false; } int Hungarian() { // 初始化vertex labeling // memset(lx, 0, sizeof(lx)); // 任意值皆可 memset(ly, 0, sizeof(ly)); for (int x=0; x<X; ++x) for (int y=0; y<Y; ++y) if (adj[x][y] != 1e9) lx[x] = max(lx[x], adj[x][y]); // X側每一個點，分別建立等邊交錯樹。 memset(mx, -1, sizeof(mx)); memset(my, -1, sizeof(my)); for (int x=0; x<X; ++x) while (true) { // 建立等邊交錯樹 memset(vx, false, sizeof(vx)); memset(vy, false, sizeof(vy)); if (DFS(x)) break; // 計算最小差值 // 窮舉交錯樹內的X、交錯樹外的Y。 int d = 1e9; for (int x=0; x<X; ++x) if (vx[x]) for (int y=0; y<Y; ++y) if (!vy[y]) if (adj[x][y] != 1e9) d = min(d, lx[x] + ly[y] - adj[x][y]); // 未新增等邊。無擴充路徑。無完美匹配。 if (d == 1e9) return -1e9; // 調整權重。樹上偶點減d，樹上奇點加d。 for (int x=0; x<X; ++x) if (vx[x]) lx[x] -= d; for (int y=0; y<Y; ++y) if (vy[y]) ly[y] += d; } // 計算最大權完美匹配的權重 int weight = 0; for (int x=0; x<X; ++x) weight += adj[x][mx[x]]; return weight; }

找出一個最大權完美二分匹配

交錯樹的建立過程，宛如最小生成樹的Prim's Algorithm，宛如最短路徑樹的Label Setting Algorithm。運用表格、Priority Queue、Bucket Sort得以降低時間複雜度。例如建立表格記錄最小差值，時間複雜度降為O(V³)。

const int X = 50; // X的點數，等於Y的點數 const int Y = 50; // Y的點數 int adj[X][Y]; // 精簡過的adjacency matrix int lx[X], ly[Y]; // vertex labeling int mx[X], my[Y]; // X各點的配對對象、Y各點的配對對象 int q[X], *qf, *qb; // BFS queue int p[X]; // BFS parent，交錯樹之偶點，指向上一個偶點 bool vx[X], vy[Y]; // 記錄是否在交錯樹上 int dy[Y], pdy[Y]; // 表格 // relaxation void relax(int x) { for (int y=0; y<Y; ++y) if (adj[x][y] != 1e9) if (lx[x] + ly[y] - adj[x][y] < dy[y]) { dy[y] = lx[x] + ly[y] - adj[x][y]; pdy[y] = x; // 記錄好是從哪個樹葉連出去的 } } // 調整權重、調整表格 void reweight() { int d = 1e9; for (int y=0; y<Y; ++y) if (!vy[y]) d = min(d, dy[y]); for (int x=0; x<X; ++x) if ( vx[x]) lx[x] -= d; for (int y=0; y<Y; ++y) if ( vy[y]) ly[y] += d; for (int y=0; y<Y; ++y) if (!vy[y]) dy[y] -= d; } // 擴充路徑 void augment(int x, int y) { for (int ty; x != -1; x = p[x], y = ty) { ty = mx[x]; my[y] = x; mx[x] = y; } } // 延展交錯樹：使用既有的等邊 bool branch1() { while (qf < qb) for (int x=*qf++, y=0; y<Y; ++y) if (!vy[y] && lx[x] + ly[y] == adj[x][y]) { vy[y] = true; if (my[y] == -1) { augment(x, y); return true; } int z = my[y]; *qb++ = z; p[z] = x; vx[z] = true; relax(z); } return false; } // 延展交錯樹：使用新添的等邊 bool branch2() { for (int y=0; y<Y; ++y) { if (!vy[y] && dy[y] == 0) { vy[y] = true; if (my[y] == -1) { augment(pdy[y], y); return true; } int z = my[y]; *qb++ = z; p[z] = pdy[y]; vx[z] = true; relax(z); } } return false; } int Hungarian() { // 初始化vertex labeling // memset(lx, 0, sizeof(lx)); // 任意值皆可 memset(ly, 0, sizeof(ly)); for (int x=0; x<X; ++x) for (int y=0; y<Y; ++y) lx[x] = max(lx[x], adj[x][y]); // X側每一個點，分別建立等邊交錯樹。 memset(mx, -1, sizeof(mx)); memset(my, -1, sizeof(my)); for (int x=0; x<X; ++x) { memset(vx, false, sizeof(vx)); memset(vy, false, sizeof(vy)); memset(dy, 0x7f, sizeof(dy)); qf = qb = q; *qb++ = x; p[x] = -1; vx[x] = true; relax(x); while (true) { if (branch1()) break; reweight(); if (branch2()) break; } } // 計算最大權完美匹配的權重 int weight = 0; for (int x=0; x<X; ++x) weight += adj[x][mx[x]]; return weight; }

UVa 11383 1411

最大權最大二分匹配

化作最大權完美二分匹配：假設X大Y小。Y側，補X-Y個點、連X(X-Y)條零邊。

最大權二分匹配

化作最大權最大二分匹配：最大權二分匹配不必有負邊，預先捨棄圖上所有負邊。

最小權完美二分匹配

化作最大權完美二分匹配：邊權重變號。

演算法

建立等邊交錯樹，額外考慮花。

每當形成花，就把花上所有點標記為偶點，並進行縮花。每當調整權重，偶點減d、奇點加d，此舉造成花上的每條匹配邊，皆與實際上的權重值少了2d。

必須記錄這失去的2d。額外建立一組blossom labeling，最初為0；每當調整權重，就加減2d。

等邊的定義改成：

l(x) + l(y) + ∑ b(B) = adj(x,y)
              包含邊(x,y)的所有花B。

調整權重改成：

d = min { l(x) + l(y) + ∑ b(B) - adj(x,y) }     x為樹上一點、y為樹外一點

l(x) -= d     x為樹上偶點
l(x) += d     x為樹上奇點

b(B) += 2d    B為最外層偶花
b(B) -= 2d    B為最外層奇花

時間複雜度O(VVE)。運用表格、Priority Queue、Bucket Sort得以降低時間複雜度。例如建立表格記錄最小差值，時間複雜度降為O(V³)。

《Data Structures for Weighted Matching and Nearest Common Ancestors with Linking》

http://vfleaking.blog.uoj.ac/blog/339