二分图最大匹配

二分图最大匹配

做法不唯一。

匈牙利算法

n1为左部分的结点，n2为右，m为边数。
贪心的思想。G邻接表存图，但注意边是有向边(n1指向n2)，match[i]表示右边部分的结点是否被匹配。
大致思路就是：枚举n1里的结点，为它配对，在n2中寻找配对点，find()函数用来实现此功能，若能成功配对，返回1；否则返回0。枚举n1里的结点i所指向的所有结点j，若该结点未被匹配，那么i就匹配这个了，返回1即可；若该结点已经被匹配到了，即被匹配的结点是n1里的match[j]，那么再想办法为match[j]寻找新的配对结点，若能找到，则一切皆好，，，否则该结点跳过，，。

时间复杂度O(nm)
AcWing863 二分图的最大匹配

#include <iostream>
#include <cstring>
using namespace std;
const int N = 505;
int n1,n2,m;
int G[N][N],match[N];
int st[N];
bool find(int x){
    for (int i=1;i<=n2;i++) if (G[x][i] && !st[i]){
        st[i] = 1;
        if (!match[i] || find(match[i])){
            match[i] = x;
            return true;
        }
    }
    return false;
}
int main(){
    int a,b;
    cin >> n1 >> n2 >> m;
    while (m--){
        cin >> a >> b;
        G[a][b] = 1;
        //G[b][a] = 1;
    }
    int res = 0;
    for (int i=1;i<=n1;i++){
        memset (st,0,sizeof st);
        if (find(i))    res++;
    }
    cout << res;
    return 0;
}