匈牙利算法算法笔记

xiaoxiaoxia · 2024-01-07 11:31:44 · 算法·理论

匈牙利算法

其实我们可以看做一个月老在牵红线，现在左边是男生，右边是女生，互相都有心仪的对象，我们就要尽量每一个男生都好。然后就出现了一个图。

我们先看第一个男生，他有两个心仪的对象，先看第一个女生，还是单身，那就选第一个，然后看下一位，也是第一个单身，就她了。但是第三位男生就出问题了，他只有一位心仪的对象，但是呢，那位已经有对象了，但是这位男生还是不放弃，找到那个男朋友，说：“要不你换一换”。我们再一看，确实还有一个备胎单身，就换一个，这样两个人都好，最后一个也很正常，直接匹配。所以总结出十六字真言：待字闺中，据为己有；名花有主，求他放手。 所以说这也告诉我们不要轻易放弃，最后悔的不是做错，而是错过。

代码实践

#include<bits/stdc++.h>
using namespace std;
const int N=510,M=100010;
int n1,n2,m;
int h[N],e[M],ne[M],idx;
int match[N];
bool st[N];
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]))//如果单身
            {
                match[j]=x;//在一起
                return true;
            }
        }
    }
    return false;//可惜，下次再来
}
int main()
{
    scanf("%d%d%d",&n1,&n2,&m);
    memset(h,-1,sizeof h);
    while(m--)
    {
        int a, b;
        scanf("%d%d",&a,&b);
        add(a,b);
    }
    int res=0;
    for(int i=1;i<=n1;i++)
    {
        memset(st,false,sizeof(st));
        if(find(i))//开始相亲
            res++;
    }
    printf("%d\n",res);
    return 0;
}