# 二分圖最大匹配

* 一個二分圖中，可以用邊兩兩配對的最大匹配數
* 最小點覆蓋=最大匹配
* 最大獨立集=n-最大匹配

> 如果一張圖可以分成兩群，而這兩群的邊都是連到另一群的，也就是不會連到自己

Augmenting Path Algorithm
---
:::info
交錯路徑：一條路徑中，已配對的邊和沒配對的邊相互交錯連接
增廣路徑：一個交錯路徑，但是頭尾都是未配對的邊
:::

* 增廣路徑中，把已配對的邊變成未配對，未配對變成已配對，這時配對數量一定會增
加1個（**種樹問題**）
* 原本的增廣路徑路徑：
* 互換後的增廣路徑：

* 所以作法是：枚舉每個左邊的點，dfs找從這一點開始的增廣路徑。如果找到就加一（包只有一個邊但未配對的），然後遞迴回去把配對互換。
* 如果找不當增廣路徑的話就結束
* $O(mn)$

#include <bits/stdc++.h>
#define EB emplace_back
#define vci vector<int>
#define PII pair<int,int>
#define F first
#define S second
#define rep(X, a,b) for(int X=a;X<b;++X)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) (int)(a).size()
#define NL "\n"
#define LL long long

using namespace std;

//lm: left node pairs, right node pairs, done:visited
vector<int> lm, rm, done;
vector<vector<int>> lg;// edges from the left

bool dfs(int nd){
    done[nd]=1;
    for(auto a:lg[nd]){
        if(rm[a]==-1 || (!done[rm[a]] && dfs(rm[a]))){
            lm[nd]=a;
            rm[a]=nd;
            return 1;
        }
    }
    return 0;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m, k; // left nodes:n, right nodes:m, edges:k
    cin>>n>>m>>k;
    lm.resize(n, -1);
    rm.resize(m, -1);
    done.resize(n);
    lg.resize(n);
    
    int a, b;
    rep(i,0,k){
        cin>>a>>b;
        a--, b--;
        lg[a].EB(b);
    }
    
    LL ans=0;
    rep(i,0,n){
        fill(ALL(done), 0);
        if(dfs(i)) ans++; //有增廣路徑
    }
    cout<<ans<<NL;
}

網路流
---
* 問題可以轉為最大網路流
* 設一個起點，連到二分圖左邊所有的點
* 二分圖右邊所有點則連到一個終點
* 所有邊（包括二分圖裡）都設最大流量為1
* 因此每個左邊每個點最多只會從起點連進1個邊，然後右邊所有的點最多只有一個邊能流出去到終點


* dinic: $O(\sqrt{n}m)$