[编程笔记]-Bipartite_Graph_Maximum_Match(Hungary_Algorithm)二分图最大匹配（匈牙利算法）

二分图最大匹配

就是求出在二分图中，最多有多少对点能完成匹配。

有时还会让你输出方案。

更高级的其实是带权的匹配问题，但鉴于这篇博客本意不在于此，所以就只讲解匈牙利算法了。

当然还有更高级的我忘了，到时候再说吧。

匈牙利算法

其实很简单，以左侧点为基准，对于每个点，尝试每个与它相连的右侧点：

如果右侧点没有匹配，那就直接上；如果右侧点有匹配了，就让跟它匹配的左侧点尝试找别的可以匹配的点（也就是递归），成了，就让那个点换一个匹配点，然后自己匹配上去；不成，那就接着试下一个点。

如果一个左侧点没法连上任何右侧点，即视为无法进行匹配。在某些题型中，就是匹配失败了。

y总の奇妙讲解belike: 一边男的，一边女的，男的找女的，如果就可能，就让她原配换一个，然后自己上去。实在换不了，自己再换一个对象。所以人嘛都要试一试，不能轻易放弃，要克服困难~

代码

还是上道题感受一下问法：
AcWing861-二分图的最大匹配

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

const int N=505,M=1e5+5;

int idk,hd[N],to[M],ne[M];

int n1,n2,m;
int u,v;
bool fns[N]={false};
int ma[N];

void merge(int a,int b){
    to[++idk]=b;
    ne[idk]=hd[a];
    hd[a]=idk;
}

bool find(int x){
    fns[x]=true;
    for(int i=hd[x];i;i=ne[i]){
        if(ma[to[i]]==0||(!fns[ma[to[i]]]&&find(ma[to[i]]))){
            ma[to[i]]=x;
            return true;
        }
    }
    return false;
}

int hungary(){
    int res=0;
    for(int i=1;i<=n1;i++){
        memset(fns,0,sizeof(fns));
        if(find(i))res++;
    }
    return res;
}

int main(){
    cin>>n1>>n2>>m;
    while(m--){
        cin>>u>>v;
        merge(u,v);
    }
    cout<<hungary();
    return 0;
}

完结撒花o(￣︶￣)o