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

发布时间:2020-07-31 01:22:13 作者:oldpman
来源:网络 阅读:1203

将写代码过程中重要的一些代码片段珍藏起来,如下的代码是关于C语言[二分图最大匹配] 匈牙利算法的代码,应该是对各位有一些好处。

const int INF = 0x3f3f3f3f; 
const int MAXN=510;
{
    int v;
    {
        {
            used[v]=true;
            {
                link[v]=u;
                return true;
            }
        }
    }
    return false;
}
int hungary()
{
    int res=0;
    int i,u;
    memset(link,-1,sizeof(link));
    for(u=0;u<uN;u++)
    {
        memset(used,0,sizeof(used));
        if(dfs(u)) 
            res++;
    }
    return res;
}   

以上是匈牙利算法的关键代码其实实现就是一个找增广路径的过程增广路径字面意思就是把路径越增越广实际意思也是一样的DFS从左边起始点开始搜索1.右边如果没匹配就匹配(link[v]==-1)2.如果右边匹配过了...就从右边点找左边的匹配点再搜索看是否能增广以上两种情况都能使匹配边+1这就是找二分图最大匹配的最简单算法了,代码很短,时间复杂度为O(n^3),网络流当然也能实现咯...记住咯:最小点覆盖=二分图最大匹配最小路径覆盖=|P|-二分图最大匹配PS:网络流还没看...悲剧...滚去看DINIC了...

推荐阅读:
  1. 什么和算法的执行效率有关
  2. 什么是算法

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

算法 代码

上一篇:app性能测试之TraceView

下一篇:javascript与php对json的操作

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》