# Matching 演算法
## 二分圖最大匹配
- 給定一個不完美的二分圖，找出最大匹配數
- 可以直接用 flow 觀點，增加兩個點 source 及 destination 解決
- 演算法即為不斷找出增廣路徑
- `最小點覆蓋 = 最大匹配`

#include <bits/stdc++.h>
using namespace std;

vector <int> G[100];
bool visited[100];
int match[100];     // 只記錄右側的點 matching

bool dfs(int now){
    for(auto &nb:G[now]){
        if(visited[nb]) continue;
        visited[nb] = true;
        if(match[nb]==-1 || dfs(match[nb])){    // 鄰居還沒匹配，或可以修改
                                                // 注意是對 match[nb] 做 DFS
            match[nb] = now;
            return true;
        }
    }
    return false;
}

int bipartite_matching(int n){
    int ans = 0;
    memset(match, -1, sizeof(match));
    for(int x = 1; x <= n; x++){        // 只對左側的點找增廣
        memset(visited,false,sizeof(visited));
        if(dfs(x))  ans++;
        for(int i=1;i<=8;i++)   cout<<match[i]<<" "; cout<<endl;
    }
    return ans;
}

int main(){
    vector<vector<int>> input = {{1,5},{1,7},{2,5},{3,5},{3,6},{4,7},{4,8}};
    for(auto e:input){
        G[e[0]].push_back(e[1]);
        G[e[1]].push_back(e[0]);
    }
    cout<<bipartite_matching(4)<<endl;
    return 0;
}

- 類似作法可以推廣到一般圖最大匹配，但細節過於複雜
## 完美二分圖最大權匹配
- The Hungarian matching algorithm / Kuhn-Munkres algorithm
- https://brilliant.org/wiki/hungarian-matching/#
- https://omeletwithoutegg.github.io/2020/11/16/Maximum-Weight-Bipartite-Matching/
- https://www.cc.gatech.edu/~rpeng/18434_S15/hungarianAlgorithm.pdf

#include <bits/stdc++.h>
using namespace std;


const int N = 125;
int n;
int g[N][N];
int lx[N], ly[N];           // labeling function
int visx[N], visy[N];       
int match[N];               // match[j] = i 


void addEdge(int a, int b, int weight) {
    g[a][b] = max(g[a][b], weight);
}

bool dfs(int i) {
    if(visx[i]) return false;
    visx[i] = true;
    for(int j = 0; j < n; j++) {
        if(visy[j])                         continue;
        if(lx[i] + ly[j] - g[i][j] != 0)    continue;
        
        visy[j] = true;
        if(match[j] == -1 || dfs(match[j])) {
            match[j] = i;
            return true;
        }
    }
    return false;
}

bool augment(int x) {   // 從 x 出發，沿著 Gl 找增廣路徑
    for(int i = 0; i < n; i++) visx[i] = visy[i] = false;
    return dfs(x);
}

void relabel() {        // 找不到增廣路徑時，調整 Gl
    int delta = 1e9;
    for(int i = 0; i < n; i++) if(visx[i])
        for(int j = 0; j < n; j++) if(!visy[j])
            delta = min(delta, lx[i] + ly[j] - g[i][j]);
        
    for(int i = 0; i < n; i++) if(visx[i]) lx[i] -= delta;
    for(int j = 0; j < n; j++) if(visy[j]) ly[j] += delta;
}


int solve() {
    for(int i = 0; i < n; i++) {
        lx[i] = ly[i] = 0;
        for(int j = 0; j < n; j++) 
            lx[i] = max(lx[i], g[i][j]);
    }
    for(int i = 0; i < n; i++) match[i] = -1;
    
    // The Key algorithm
    for(int i = 0; i < n; i++){
        while(!augment(i))      // 為 i 找到 matching
            relabel();          // 如果當下找不到，則每次 relabel ，可以把一個 y_j 納入考慮
                                // 因此 n 次 relabel，必定都納入考慮，必定可以增廣
            
        cout<<"--------\n";
        for(int ii = 0; ii < n; ii++)   cout<<lx[ii]<<((ii==n-1)?'\n':' ');
        for(int jj = 0; jj < n; jj++)   cout<<ly[jj]<<((jj==n-1)?" -> ":" ");
        for(int jj = 0; jj < n; jj++)   cout<<match[jj]<<((jj==n-1)?"\n":" ");
    }
    
    int ans = 0;
    for(int j = 0; j < n; j++)  if(match[j] != -1)  ans += g[match[j]][j];
    return ans;
}

int main(){
    n = 4;
    addEdge(0,0,3);addEdge(0,1,4);addEdge(0,2,5);addEdge(0,3,6);
    addEdge(1,0,5);addEdge(1,1,3);addEdge(1,2,4);addEdge(1,3,7);
    addEdge(2,0,6);addEdge(2,1,5);addEdge(2,2,6);addEdge(2,3,3);
    addEdge(3,0,2);addEdge(3,1,8);addEdge(3,2,5);addEdge(3,3,7);
    
    cout<<solve();
    return 0;
}