匈牙利算法和KM算法的总结/扩展阅读

Author Avatar
空気浮遊 2017年11月26日
  • 在其它设备中阅读本文章

匈牙利算法

Problem

Luogu P3386 二分图匹配

Solution

二分图不一定为无向图,只需边的两端的点可分即是二分图。这是最小边覆盖的前提条件。
匈牙利算法匹配流程:

  1. 确定二分图的两个点集,选择一个点集作为搜索起点。设为左边点。
  2. 两个数组:match, check。match 代表匹配点,check 代表一次深搜的 vis(是否被遍历)。match 建议初始化为 -1。
  3. 枚举每个左边点。如果左边点没有被匹配过(match 为 -1),进行深搜匹配。最大匹配不会超过左边点的个数,因此每次深搜最多只增加一对匹配。

    I. 枚举相邻的右点。如果没有被匹配过则直接返回,因为已经增加一对匹配。如果被匹配过了则深搜到右点的匹配点,看看是否有点没被匹配,持续下去。必须找到一个没被匹配的右点,才能形成增广路。

    II. 若找到没被匹配过的点或深搜的点返回了 true,更新匹配,返回 true。代表这是一个增广路。

    III. 若啥也没找到返回 false。代表找不到增广路。

  4. 若深搜左边点返回 ture,答案计数 +1. 代表找到了增广路。

Codes

#include<bits/stdc++.h>
using namespace std;

const int N=2010,M=8e6+10;
int h[N],to[M],nexp[M],p=1;
inline void ins(int a,int b){
    nexp[p]=h[a],h[a]=p,to[p]=b,p++;
}

bool check[N];
int match[N];

bool dfs(int x){
    for(int u=h[x];u;u=nexp[u]){
        if( !check[to[u]] ){
            check[to[u]]=1;
            if( match[to[u]]==-1 || dfs(match[to[u]]) ){
                match[to[u]]=x;
                match[x]=to[u];
                return true;
            }
        }
    }
    return false;
}

int main(){
    ios::sync_with_stdio(false);
    int n,m,e;
    cin>>n>>m>>e;
    int u,v;
    for(int i=0;i<e;i++){
        cin>>u>>v;
        if(v>m) continue;
        v+=n;
        ins(u,v),ins(v,u);
    }
    memset(match,-1,sizeof(match));
    int ans=0;
    for(int i=1;i<=n;i++){
        if(match[i]==-1){
            memset(check,0,sizeof(check));
            if(dfs(i)) ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

扩展阅读

Renfei Song's Blog - 二分图的最大匹配、完美匹配和匈牙利算法

ACDreamer 的匈牙利算法详解

二分图中对最小顶点覆盖、最小边覆盖、最大独立集的理解

KM 算法 - 带权二分图最佳匹配

前提,二分图左侧端点数 <= 右侧端点数

-1、说明

为了方便记忆和记录使用了大量看上去令人很害怕的数学符号。虽然基本算是乱用。
以及只讲了怎么做没讲为什么,也没说如何理解。
所以建议在理解的情况下再按下方的描述进行记忆 / 加深理解流程。
实际上以下应该只算是笔记 2333
如果想学习 KM 算法,请直接翻至最下方的扩展阅读。

0、概括

其实就是匈牙利算法的扩展。同时引入了 相等子图 以及 顶标 等概念。
在这里我们称顶标为 期望

1、数组的初始化

check 标记:每次深搜的遍历情况
match 匹配:右侧端点匹配的点
以上数组与匈牙利算法基本相同。下面为新引入的数组:
ex 期望:每个点的期望值
slack 最小期望差:左侧端点 ex 减少 slack 可使相等子图增加至少一个右侧点。

2、完备匹配

左侧点 / 右侧点至少有一边全部匹配,则称此匹配为完备匹配。

3、最佳匹配

带权二分图中权值和最大的完备匹配称为最佳匹配。
最佳匹配不等于最大权匹配。

4、相等子图 - $G'$

令左侧为 X 侧,右侧为 Y 侧。
则 $ex_{x_{i}}+ex_{y_j}=w (x_i , y_j)$ 的边 $(X_i,Y_j)$ 存在于 $G'$ 中。

5、流程

初始化 $ex_{x_i}=max(w(x_i,y_j))\ ,\ ex_{y_i}=0$ 。
针对每个 $X_i$ 在 $G'$ 中寻找增广路。

每次寻找增广路过程中, $slack=INF$ 。
若不存在增广路,则形成由许多交错路构成的交错树 $T$ 。在寻找增广路过程中,针对 $x_i \in T,\ y_j \notin G',\ (x_i,y_j) \in G$ ,更新 $slack=min(slack,\ w(x_i,y_j))$ 。
则针对每个 $x_i,y_j \in T,\ ex_{x_i}-=slack,\ ex_{y_j}+=slack$ 。
若 $x_i \in T,\ y_j \notin G'$,则 $ex_{x_{i}}+ex_{y_j}$ 减小,说明边 $(x_i, y_j)$ 可能加入 $G'$。
而 $slack$ 的取值尽量只让 $G'$ 扩充一条边。
扩充 $G'$ 之后,重复寻找增广路。

每个 $x_i$ 都找到增广路之后,则形成最佳匹配。

扩展阅读 / 引用文章

KM 算法详解 + 模板 - 段文弱
上面这篇个人认为讲的很有趣,很好理解。但代码相较下方文章稍显冗长。
KM 算法 - C20180630_zjf
本文叙述的大部分概念都引自上文。实际上本文只是上文的精简版。代码精简好背,而且也比较好理解。

练习题目

Luogu P1559 运动员最佳匹配问题
KM 算法模板题。

Codes:

#include<bits/stdc++.h>
#define INF (0x7fffffff)
using namespace std;

const int N=25;
int w[N][N];
int match[N];
int vis_l[N];
int vis_r[N];
int ex_l[N];
int ex_r[N];
int slack;
int n;

bool dfs(int x){
    vis_l[x]=1;
    int gap;
    for(int i=1;i<=n;i++){
        if(vis_r[i]) continue;
        gap=ex_l[x]+ex_r[i]-w[x][i];
        if(gap==0) {
            vis_r[i]=1;
            if(match[i]==-1 || dfs(match[i])){
                match[i]=x;
                return true;
            }
        }
        else if(gap>0)slack=min(slack,gap);
    }
    return false;
}

inline int KM(){
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        ex_l[i]=max(ex_l[i],w[i][j]);
    memset(match,-1,sizeof(match));
    for(int i=1;i<=n;i++){
        while(1){
            slack=INF;
            memset(vis_l,0,sizeof(vis_l));
            memset(vis_r,0,sizeof(vis_r));
            if(dfs(i)) break;
            for(int i=1;i<=n;i++){
                if(vis_l[i]) ex_l[i]-=slack;
                if(vis_r[i]) ex_r[i]+=slack;
            }
        }
    }
    int ret=0;
    for(int i=1;i<=n;i++)
        ret+=w[match[i]][i];
    return ret;
}

int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        cin>>w[i][j];
    int na;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++){
        cin>>na;
        w[j][i]*=na;
    }
    cout<<KM()<<endl;
    return 0;
}