C语言 [二分图最大匹配] 匈牙利算法！

傷城~ 2022-10-17 00:35 215阅读 0赞

**代码实现：**

constintINF = 0x3f3f3f3f;
    
    constintMAXN=510;
    
    intuN,vN;//u,v数目
    
    intg[MAXN][MAXN];//构图
    
    intlink[MAXN];   //link[v]=u表示右边对左边的匹配
    
    boolused[MAXN];//是否访问过
    
    booldfs(intu)//从左边开始找增广路径
    
    {
    
        intv;
    
        for(v=0;v<vN;v++)//右边顶点编号从0开始
    
        {
    
            if(g[u][v]&&!used[v])  //如果存在通路,且从u开始搜索时该点没访问过
    
            {
    
                used[v]=true;
    
                if(link[v]==-1 || dfs(link[v])) //找增广路
    
                {
    
                    link[v]=u;
    
                    returntrue;
    
                }
    
            }
    
        }
    
        returnfalse;
    
    }
    
    inthungary()
    
    {
    
        intres=0;
    
        inti,u;
    
        memset(link,-1,sizeof(link));
    
        for(u=0;u<uN;u++)
    
        {
    
            memset(used,0,sizeof(used));
    
            if(dfs(u))
    
                res++;
    
        }
    
        returnres;
    
    }

\--------------------------------------

以上是匈牙利算法的关键代码

其实实现就是一个找增广路径的过程

增广路径 字面意思就是把路径越增越广

实际意思也是一样的

**DFS从左边起始点开始搜索 **

1.右边如果没匹配就匹配(link\[v\]==-1)

2.如果右边匹配过了...就从右边点找左边的匹配点再搜索看是否能增广

以上两种情况都能使匹配边+1

这就是找二分图最大匹配的最简单算法了,代码很短,时间复杂度为O(n^3),网络流当然也能实现咯...

**记住咯: **

> 最小点覆盖 = 二分图最大匹配 
> 
> 最小路径覆盖 = |P| - 二分图最大匹配

![0e611964f47bbaa3c6283ac18bca4f6d.gif][]

不管你是转行也好，初学也罢，进阶也可，如果你想学编程，进阶程序员~

【值得关注】我的 **[编程学习交流俱乐部][Link 1] ！**【点击进入】

**C语言入门资料：**

![6b498990e77e868149a4b87438a21f1d.png][]

**C语言必读书籍：**

![2424460e8a4d3e70ea3639d13a8a166c.png][]

[0e611964f47bbaa3c6283ac18bca4f6d.gif]: /images/20221014/45b2dc9e58df492a8c99c9ef354f89c1.png
[Link 1]: https://jq.qq.com/?_wv=1027&k=RS0PvN8j
[6b498990e77e868149a4b87438a21f1d.png]: /images/20221014/a3eba28542c54a72b6a0945f635e8912.png
[2424460e8a4d3e70ea3639d13a8a166c.png]: /images/20221014/b6e155837f554f6fbc7c37c300e955f4.png