匈牙利算法

<mark>什么是匈牙利算法</mark>
匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法,并推动了后来的原始对偶方法。美国数学家哈罗德·库恩于1955年提出该算法。此算法之所以被称作匈牙利算法,是因为算法很大一部分是基于以前匈牙利数学家Dénes Kőnig和Jenő Egerváry的工作之上创建起来的。 以上均是书上语言,简单来说匈牙利算法就是用来求解二分图匹配问题 的;
<mark>思路</mark>
接下来我们来说一下匈牙利算法的思路,匈牙利算法主要是通过,不断地寻找增广路(增广路径的定义:设M为二分图G已匹配边的集合,若P是图G中一条连通两个未匹配顶点的路径(P的起点在X部,终点在Y部,反之亦可),并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现,则称P为相对于M的一条增广路径。 )来求解的,

如图左侧为3个女生,右侧为三个男生,连线代表女生对男生有好感可以匹配;
那么我们来为女生匹配男朋友,
本着匹配一对情侣胜造七级浮屠的原则匈牙利算法教你这样做

========================================================================================
首先我们为一号女生匹配,每次匹配过程中我们都要遍历一遍所有男生,一号女生对一号男生有好感可以匹配,成功为一号
女生找到男朋友,接下来看二号女生二号女生对一号男生有好感,可以匹配,匹配成~等等,一号男生名草有主了,怎么办呢?
于是二号女生找到一号女生,“你可以换一个男朋友么?”于是继续遍历壹号女生有好感的男生发现一号女生可以和二号男生匹配
(寻找增广路的过程),那么一号女生和二号男生匹配,二号女生和一号男生匹配成功,接下来看三号女生发现三号女生可以和三号男生匹配,并且三号男生没有女朋友,匹配成功,至此找男朋友结束。那么最大匹配值为3;

==============================================================================================
这个过程看似很麻烦,实际上就是一个递归的过程;
接下来上代码

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

const int maxn = 200;

int e[maxn][maxn], visit[maxn], cy[maxn];
int t, n, m;

int dfs(int u)//dfs寻找增广路
{
    for(int i = 1; i <= n; i++)//为女生匹配男生,遍历每一个男生
    {
        if(e[u][i] == 1 && !visit[i])//如果女生对男生有好感而恰巧男生有没有女朋友那么直接匹配
        {
            visit[i] = 1;//标记男生,每个男生只能被使用一次
            if(cy[i] == -1 || dfs(cy[i]))//如果男生没有被匹配(-1)就直接匹配,否则寻找增广路,
            {
                cy[i] = u;
                return 1;
            }
        }
    }
    return 0;
}

int main()
{
    scanf("%d", &t);
    int a, b;
    while(t--)
    {
        scanf("%d %d", &n, &m);
        memset(e, 0, sizeof(e));
        memset(cy, -1, sizeof(cy));
        for(int i = 1; i <= m; i++)
        {
            scanf("%d %d", &a, &b);
            e[a][b] = 1;
        }
        int ans = 0;
        for(int i = 1; i <= n; i++)
        {
            memset(visit, 0, sizeof(visit));//每次都需要对标记数组清空;
            ans += dfs(i);
        }
        printf("%d\n", ans);
    }
    return 0;
}

原创