補個vector存圖法

• 模板題 ZJ c889

• 模板題 TIOJ 1209

• CF 557D

• CF 1144F

二分圖 Bipartite Graph

定義

• 將所有點分成兩個集合，不存在連接同集合中兩點的邊

判定

• 著色法：

  • 使用DFS以兩個顏色著色，嘗試將任意相鄰兩點塗上不同顏色
  • 如果發現有一點跟「相鄰且已經塗色的點」同一顏色，則二分圖不成立，反之成立

• 實作：

  • 紀錄每個點的顏色（紅、藍、未塗色），並使用DFS走訪塗色＋判定

匹配 Matching

定義

• 在圖上找一組邊，任兩條邊沒有公用點

• 完美匹配、最大匹配、最大邊權匹配。。。

匈牙利算法 Hungarian algorithm

• ZJ c455

• UVA 10080

用途

• 無邊權二分圖上找最大匹配(邊數最多)

交替路徑和增廣路徑

• 交替路徑：選一個點當起點，沿著(邊)未匹配、匹配交替走

1 -> 5 -> 2

未匹配、匹配邊對調，匹配數不變

• 增廣路徑：在走交替路徑的途中遇到未匹配的點(兩端皆未匹配)

1 -> 7 -> 4 -> 8

未匹配、匹配邊對調，匹配數+1

匈牙利樹

• 從一個點開始走交替路徑直到無法再擴展為止，且葉節點已匹配，形成的樹

實作

• 找到增廣路徑 -> 對調匹配、未匹配邊

• 找到匈牙利樹 -> 刪除(不看)

• 無增廣路徑即為最大匹配

網路流實作二分圖匹配

最大基數匹配(Maximum cardinality bipartite matching)

將問題轉化成最大流問題

1. 增加源點s與匯點t

2. 建立弧連接s和X中每一點，方向由s指向X

3. 建立弧連接

   $t$和Y中每一點，方向由Y指向t

4. 將原二分圖中的每條邊改為弧，方向由X指向Y

5. 將每條弧容量設定為1

• 求最大流，路徑中原圖的邊形成的邊集即為最大基數匹配

最大權完美匹配(Maximum weighted perfect matching)

將問題轉化為最大費用最大流問題

1. 增加源點

   $s$與匯點
   $t$

2. 建立弧連接

   $s$和X中每一點，方向由
   $s$指向X，容量設定為1，費用設定為0

3. 建立弧連接

   $t$和Y中每一點，方向由Y指向
   $t$，容量設定為1，費用設定為0

4. 將原二分圖中的每條邊改為弧，方向由X指向Y，容量設定1，費用設定為原邊權

• 求最大費用最大流，路徑中原圖的邊形成的邊集即為最大權完美匹配