前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >带权二分图最优匹配(KM)

带权二分图最优匹配(KM)

作者头像
AngelNH
发布2020-04-16 15:45:08
4K0
发布2020-04-16 15:45:08
举报
文章被收录于专栏:AngelNI

云止水中,动寂适宜。

KM算法

KM算法是在匈牙利算法的基础上衍生,在二分图匹配的问题上增加权重,变成了一个带权二分图匹配问题,求最优的二分图匹配。

KM算法讲解,这篇博客自我感觉很好理解。

二分图的带权匹配就是求出一个匹配集合,使得集合中边的权值之和最大或最小。

而二分图的最优匹配则一定为完备匹配,在此基础上,才要求匹配的边权值之和最大或最小。二分图的带权匹配与最优匹配不等价,也不互相包含。

我们可以使用KM算法实现求二分图的最优匹配。KM算法可以实现为O(N^3)。

KM的几种转化

KM算法是求最大权完备匹配,如果要求最小权完备匹配怎么办?方法很简单,只需将所有的边权值取其相反数,求最大权完备匹配,匹配的值再取相反数即可。 KM算法的运行要求是必须存在一个完备匹配,如果求一个最大权匹配(不一定完备)该如何办?依然很简单,把不存在的边权值赋为0。 KM算法求得的最大权匹配是边权值和最大,如果我想要边权之积最大,又怎样转化?还是不难办到,每条边权取自然对数,然后求最大和权匹配,求得的结果a再算出e^a就是最大积匹配。****

练习

HDU2255

板子

代码语言:javascript
复制
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<stack>
#include<cstdlib>
#include<cctype>
#define ll long long
#define ld long double
#define rep(i,a,b) for(int i = a;i<=b;++i)
#define mem(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f

using namespace std;
const int N = 110;
int n;
int weight[N][N];
int cx[N],cy[N];
bool sx[N],sy[N];
int match[N];

inline int read()
{
    int num = 0, w=0;char ch=0;
    while(!isdigit(ch)) {w|=ch=='-';ch = getchar();}
    while(isdigit(ch)){num = (num<<3) + (num<<1) + (ch^48);ch = getchar();}
    return w? -num: num;
}
inline void write(int x)
{
    if(x<0){putchar('-');x = -x;}
    if(x>9) write(x / 10);
    putchar(x % 10 + '0');
}
void fast()
{ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
int dfs(int u)
{
    sx[u] = 1;
    rep(v,1,n)
    {
        if(!sy[v]&&cx[u]+cy[v]==weight[u][v])
        {
            sy[v] = 1;
            if(match[v]==-1||dfs(match[v]))
            {
                match[v] = u;
                return 1;
            }
        }
    }
    return 0;
}
int km(bool max_weight)
{
    if(!max_weight)//如果求最小匹配,权值取反
    {
        rep(i,1,n)
        {
            rep(j,1,n)
            {
                weight[i][j] = - weight[i][j];
            }
        }
    }
    //初始化顶标,cx[i] = max(weight[i][j]|j=1,2,3...n)cy[i] = 0;
    rep(i,1,n)
    {
        cy[i] = 0;
        cx[i] = -INF;
        rep(j,1,n)
        {
            if(cx[i]<weight[i][j])
            {
                cx[i] = weight[i][j];
            }
        }
    }
    mem(match,-1);
    //不断修改顶标,直到找到完备或完美匹配
    rep(u,1,n)//为x里的每一个点找到匹配
    {
        while(1)
        {
            mem(sx,0);
            mem(sy,0);
            if(dfs(u))//若x[u],在相等子图找到匹配,继续为下一个点找匹配
                break;
            //如果没在相等子图里找到匹配,就修改顶标,直到找到匹配为止
            //首先找到修改顶标时的增量inc,min(cx[i]+cy[i]-weight[i][j],inc)
            //cx[i] 为搜索过的点,cy[i]是未搜索过的点,
            //因为现在是要给u找匹配,所以只需要修改找的过程中搜索过的点,增加有可能对u有帮助的边
            int inc = INF;
            rep(i,1,n)
            {
                if(sx[i])
                {
                    rep(j,1,n)
                    {
                        if(!sy[j]&&((cx[i]+cy[i]-weight[i][j])<inc))
                        {
                            inc = cx[i]+cy[i]-weight[i][j];
                        }
                    }
                }
            }
            //找到增量后修改顶标,因为sx[i]与sy[j]都为真,则必然符合cx[i]+cy[j] = weight[i][j],
            //然后cx[i]-inc,cy[j]+inc,不会改变等式,但是原来的cx[i]+cx[j]!=weight[i][j],
            //即sx[i]与sy[j]最多一个为真,cx[i]+cy[j]就会发生改变,从而符合等式,边也就加入相等子图
            rep(i,1,n)
            {
                if(sx[i])
                    cx[i]-=inc;
                if(sy[i])
                    cy[i]+=inc;
            }

        }
    }
    int sum = 0;
    rep(i,1,n)
    {
        if(match[i]>0)
        {
            sum+=weight[match[i]][i];
        }
    }
    if(!max_weight)
        sum = -sum;
    return sum;
}
int main()
{
   while(cin>>n)
   {
       rep(i,1,n)
       {
           rep(j,1,n)
           {
               cin>>weight[i][j];
           }
       }
       cout<<km(1)<<endl;
   }
   system("pause");
   return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020-03-12|,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • KM算法
  • KM的几种转化
    • 练习
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档