返回顶部

收藏

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

更多
const int INF = 0x3f3f3f3f;
const int MAXN=510;
int uN,vN;//u,v数目
int g[MAXN][MAXN];//构图
int link[MAXN];   //link[v]=u表示右边对左边的匹配
bool used[MAXN];//是否访问过
bool dfs(int u)//从左边开始找增广路径
{
    int v;
    for(v=0;v<vN;v++)//右边顶点编号从0开始
    {
        if(g[u][v]&amp;&amp;!used[v])  //如果存在通路,且从u开始搜索时该点没访问过
        {
            used[v]=true;
            if(link[v]==-1 || dfs(link[v])) //找增广路
            {
                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| - 二分图最大匹配

标签:c/c++

收藏

0人收藏

支持

0

反对

0

相关聚客文章
  1. yuer 发表 2018-07-27 08:46:07 coredump之百米之内必有解药
  2. hev 发表 2018-04-28 06:11:38 一个简单、轻量的 Linux 协程实现
  3. hev 发表 2017-10-19 15:56:11 FSH – 助你接入私有网络中的 Linux 终端
  4. gonwan 发表 2015-04-15 08:03:07 Database Access Layer in C++
  5. gonwan 发表 2015-12-28 08:41:13 Basic Usage of Boost MultiIndex Containers
  6. gonwan 发表 2016-01-19 03:37:54 Coroutines in C++/Boost
  7. Haoxiang Li 发表 2017-10-25 20:29:02 MXNet C++ Deployment
  8. yuer 发表 2017-10-20 07:52:47 基于leveldb的持久消息队列SDK
  9. yuer 发表 2017-10-07 07:51:32 c++11完美转发
  10. 博主 发表 2016-09-03 00:00:00 C++编译期类型信息的利用
  11. yuer 发表 2017-09-06 03:03:29 libcurl访问unix socket
  12. yuer 发表 2017-09-07 08:14:58 valgrind检测php扩展的warning

发表评论