---
tags: 圖論
title: 二分圖、匹配、匈牙利算法
---
:::warning
## [補個vector存圖法](https://www.notion.so/vector-f437fa3263f840c1a21cdebe5d4384ce)
:::

:::info
- #### 模板題 [ZJ c889](https://zerojudge.tw/ShowProblem?problemid=c889)
- #### 模板題 [TIOJ 1209](https://tioj.ck.tp.edu.tw/problems/1209)
- #### [CF 557D](https://codeforces.com/problemset/problem/557/D)
- #### [CF 1144F](https://codeforces.com/problemset/problem/1144/F)
:::

:::success
# 二分圖 Bipartite Graph

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

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

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

:::success
# 匹配 Matching

## 定義


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

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

# 匈牙利算法 Hungarian algorithm

- #### [ZJ c455](https://zerojudge.tw/ShowProblem?problemid=c455)
- #### [UVA 10080](https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1021)

## 用途

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

### 交替路徑和增廣路徑

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

1 -> 5 -> 2
未匹配、匹配邊對調，匹配數不變

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

1 -> 7 -> 4 -> 8
未匹配、匹配邊對調，匹配數+1

## 匈牙利樹

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


## 實作

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

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

- 無增廣路徑即為最大匹配
:::

:::success
# 網路流實作二分圖匹配

## 最大基數匹配(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，費用設定為原邊權==

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