匈牙利算法，他可以在比較快的時(shí)間復(fù)雜度之內(nèi)告訴我們左邊和右邊成功匹配的最大數(shù)是多少

匹配指的是邊的數(shù)量，成功的匹配指的是兩個(gè)未被使用的點(diǎn)之間存在一條邊(就不存在兩條邊共用了一個(gè)點(diǎn)的)。

匈牙利算法可以返回成功匹配的最大匹配數(shù)是多少。

#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表示的是這個(gè)妹子匹配的男生是誰，0代表沒有匹配。
bool st[N];//表示這個(gè)女生是否考慮過
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]){//如果這個(gè)妹子沒有考慮過st[j]=true;//表示這個(gè)妹子已經(jīng)被考慮了if(match[j] == 0 || find(match[j])){//妹子沒有匹配的男生 或 這個(gè)男生可以找到其他的妹子代替//如果這個(gè)被替換妹子的男生的其他相連的女生被匹配了的話，會讓匹配的那個(gè)男生再去找其他妹子，就是套娃，牽一發(fā)動(dòng)所有有關(guān)系的人。每個(gè)男生進(jìn)入find都會對已經(jīng)被考慮的妹子變?yōu)閠rue，不會造成重復(fù)考慮。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);//雖然是無向邊，但只會找一下左邊點(diǎn)的所有出邊，只需要存左邊指向右邊就可以了。}int res=0;//匹配數(shù)量//就依次來分析一下每個(gè)男生，該找哪個(gè)妹子。for(int i=1;i<=n1;i++){memset(st,false,sizeof st);//每一次分析之前，清空所有妹子，表示這些妹子都還沒考慮過，保證每個(gè)妹子我只考慮一遍。if(find(i)) res++;//判斷是否能找到妹子}cout<<res<<endl;return 0;
}