【AcWing】861. 二分图的最大匹配(匈牙利算法)

匈牙利算法，他可以在比较快的时间复杂度之内告诉我们左边和右边成功匹配的最大数是多少

匹配指的是边的数量，成功的匹配指的是两个未被使用的点之间存在一条边(就不存在两条边共用了一个点的)。

匈牙利算法可以返回成功匹配的最大匹配数是多少。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;const int N=510,M=1e5+10;
int h[N],e[M],ne[M],idx;
int match[N];//match表示的是这个妹子匹配的男生是谁，0代表没有匹配。
bool st[N];//表示这个女生是否考虑过
int n1,n2,m;void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}bool find(int x){for(int i=h[x];i!=-1;i=ne[i]){//枚举看上妹子的集合int j=e[i];if(!st[j]){//如果这个妹子没有考虑过st[j]=true;//表示这个妹子已经被考虑了if(match[j] == 0 || find(match[j])){//妹子没有匹配的男生 或 这个男生可以找到其他的妹子代替//如果这个被替换妹子的男生的其他相连的女生被匹配了的话，会让匹配的那个男生再去找其他妹子，就是套娃，牵一发动所有有关系的人。每个男生进入find都会对已经被考虑的妹子变为true，不会造成重复考虑。match[j]=x;return true;   }}}return false;
}int main(){cin>>n1>>n2>>m;memset(h,-1,sizeof h);while(m--){int a,b;cin>>a>>b;add(a,b);//虽然是无向边，但只会找一下左边点的所有出边，只需要存左边指向右边就可以了。}int res=0;//匹配数量//就依次来分析一下每个男生，该找哪个妹子。for(int i=1;i<=n1;i++){memset(st,false,sizeof st);//每一次分析之前，清空所有妹子，表示这些妹子都还没考虑过，保证每个妹子我只考虑一遍。if(find(i)) res++;//判断是否能找到妹子}cout<<res<<endl;return 0;
}