# 技術｜匈牙利演算法

### 問題定義
- 給定一組工人和一組任務，每個工人執行每個任務都有一個對應的成本（或效益），目的是找到每個工人唯一指派一個任務的方式，使總成本最小（或總效益最大）。
### 演算法
- (1) 矩陣預處理：行列最小化
- (2) 使用增廣路徑演算法找到最大流
### 範例：
- 輸入資料

| - | 任務 1 | 任務 2 | 任務 3 | 任務 4 | 任務 5 |
| - | - | - | - | - | - |
| 工人1 | 9 | 11 | 14 | 11 | 7 |
| 工人2 | 6 | 15 | 13 | 13 | 10 |
| 工人3 | 12 | 13 | 6 | 8 | 8 |
| 工人4 | 11 | 9 | 10 | 12 | 9 |
| 工人5 | 7 | 12 | 14 | 10 | 14 |

- 處理 row : 7+6+6+9+7

| - | 任務 1 | 任務 2 | 任務 3 | 任務 4 | 任務 5 |
| - | - | - | - | - | - |
| 工人1 | 2 | 4 | 7 | 4 | 0 |
| 工人2 | 0 | 9 | 7 | 7 | 4 |
| 工人3 | 6 | 7 | 0 | 2 | 2 |
| 工人4 | 2 | 0 | 1 | 3 | 0 |
| 工人5 | 0 | 5 | 7 | 3 | 7 |

- 處理 column : 32 + 2

| - | 任務 1 | 任務 2 | 任務 3 | 任務 4 | 任務 5 |
| - | - | - | - | - | - |
| 工人1 | 2 | 4 | 7 | 2 | 0 |
| 工人2 | 0 | 9 | 7 | 5 | 4 |
| 工人3 | 6 | 7 | 0 | 0 | 2 |
| 工人4 | 2 | 0 | 1 | 1 | 0 |
| 工人5 | 0 | 5 | 7 | 1 | 7 |

- 使用 min cost max flow 算法 : 34+1 = 35
- 使用 Dijkstra 尋找增廣路徑

| - | 任務 1 | 任務 2 | 任務 3 | 任務 4 | 任務 5 |
| - | - | - | - | - | - |
| 工人1 | | | | | 0 |
| 工人2 | 0 | | | | |
| 工人3 | | | 0 | | |
| 工人4 | | 0 | | | |
| 工人5 | | | | 1 | |