【算法3.12】二分图 - 匈牙利算法 NTR算法（完结）

经典NTR算法！！！

让每个男生去按顺序找女生 如果该女生没有男朋友或她的男朋友有备胎 则女生把她现任绿了和这个男生在一起 

861. 二分图的最大匹配

活动 - AcWing

有 n1 个男生和 n2 个女生 (n1 ≤ 500, n2 ≤ 500)。

他们之间可以匹配的关系有 m 个 (m ≤ 1e5)。

求最大可能的匹配数

#include
#include
using namespace std;
const int N=510,M =100010;
int n1,n2,m;
int h[N],ne[M],e[M],idx;
bool st[N];
int match[N];
 
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
 
int find(int x)
{
    //遍历女孩
    for(int i=h[x];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!st[j])//如果在这一轮模拟匹配中,这个女孩尚未被预定
        {
            st[j] = true;//那x就预定这个女孩了
            //如果女孩j没有男朋友，或者她原来的男朋友能够预定其它喜欢的女孩 配对成功
            if(!match[j]||find(match[j]))
            {
                match[j] = x;
                return true;
            }
        }
    }
    return false;
}
 
int main()
{
    memset(h,-1,sizeof h);
    cin>>n1>>n2>>m;
    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<
}