KM + bfs迭代 算法

本文主要是介绍KM + bfs迭代 算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1KM算法：

能在二分图最大匹配是完美匹配时计算得出二分图最大权完美匹配，且效率一般高于网络流。缺点是有局限性。

2定义

1. 交错树：在最匈牙利算法中，如果从某个左边节点出发，寻找匹配失败，那么在dfs的过程中，所有访问过的节点，以及为了访问这些节点而经过的边，共同构成一棵树。
2. 顶标：给每个顶点的赋值，左边节点\(a_i\)，右边节点\(b_j\)，需要满足\(a_i+b_j\geq w(i,j)\)。
3. 相等子图：二分图中满足\(a_i+b_j=w(i,j)\)的边构成的子图，成为二分图的相等子图。

3定理

若相等子图中存在完备匹配，则这个完备匹配就是二分图的带权最大匹配。

4流程

对于一个交错树T，起所有的左边节点都是右边节点沿着匹配边访问到的，所有的右边节点是左边节点沿着非匹配边访问到的。

如果我们对交错树中的左边节点顶标减去一个值，右边节点顶标加上一个值，会有什么影响？

对于一条T中的匹配边来说，这条匹配边仍然属于相等子图。

对于一条非匹配边，若其左边节点在T中，则这条边有可能被加入到相等子图中去！

所以经过上述操作，左边节点可以访问到的右边节点可能增多了。

为了在改变后仍然满足顶标的性质，并保证至少有一个右边节点加入相等子图，我们选差值最小的一个进行更改；

dfs版代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<deque>
#include<cstdlib>
#include<ctime>
#define dd double
#define ld long double
#define ll long long
#define int long long
#define ull unsigned long long
#define N 5000
#define M 300000
using namespace std;

const int INF=0x3f3f3f3f;

inline int Min(int a,int b){
    return a>b?b:a;
}

inline int Max(int a,int b){
    return a>b?a:b;
}

inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

struct edge{
    int next,to,w;
    inline void intt(int to_,int ne_,int w_){
        to=to_;next=ne_;w=w_;
    }
};
edge li[M];
int head[N],tail;

inline void add(int from,int to,int w){
    li[++tail].intt(to,head[from],w);
    head[from]=tail;
}

int n,m;

int la[N],lb[N],upd[N],match[N],delta,val[N][N],ans;
bool va[N],vb[N];

inline bool dfs(int k){
    va[k]=1;
    for(int x=head[k];x;x=li[x].next){
        int to=li[x].to,w=li[x].w;
        if(!vb[to])
            if(la[k]+lb[to]==val[k][to]){
                vb[to]=1;
                if(!match[to]||dfs(match[to])){
                    match[to]=k;
                    return 1;
                }
            }
            else upd[to]=Min(upd[to],la[k]+lb[to]-val[k][to]);
    }
    return 0;
}

inline void KM(){
    for(int i=1;i<=n;i++){
        la[i]=-INF;
        for(int x=head[i];x;x=li[x].next){
            int to=li[x].to,w=li[x].w;
            la[i]=Max(la[i],w);
        }
    }
    for(int i=1;i<=n;i++)
        while(1){
            memset(va,0,sizeof(va));
            memset(vb,0,sizeof(vb));
            for(int j=1;j<=n;j++) upd[j]=INF;
            if(dfs(i)) break;
            for(int j=1;j<=n;j++)
                if(!vb[j]) delta=Min(delta,upd[j]);
            for(int j=1;j<=n;j++){
                if(va[j]) la[j]-=delta;
                if(vb[j]) lb[j]+=delta;
            }
        }
    for(int i=n+1;i<=2*n;i++) ans+=val[match[i]][i];
}

signed main(){
    n=read();m=read();
    for(int i=1;i<=m;i++){
        int from=read(),to=read(),w=read();
        add(from,to+n,w);val[from][to+n]=w;
    }
    KM();
    printf("%lld\n",ans);
    for(int i=1;i<=n;i++) printf("%lld ",match[i+n]);
    return 0;
}

但是这个代码是\(n^4\)的（随机\(n^3\)），过不了洛谷上的模板，所以我们下面讲解一下\(n^3\)的算法。

其实是一个dfs改为bfs。

仔细思考，其实dfs过程中我们做了许多重复的工作。我们考虑优化。

理解bfs的写法花了我不少时间，包括bfs的迭代做法。

下面我就bfs迭代做法开始我的讲解。

先上代码：

void bfs(int x)
{
    int a, y = 0, y1 = 0;

    for(int i = 1; i <= n; ++ i)
        p[i] = 0, c[i] = INF;

    match[y] = x;

    do{
        a = match[y], delta = INF, vb[y] = true;
        for(int b = 1; b <= n; ++ b){
            if(!vb[b]){
                if(c[b] > la[a] + lb[b] - w[a][b])
                    c[b] = la[a] + lb[b] - w[a][b], p[b] = y;
                if(c[b] < delta)//Δ还是取最小的
                    delta = c[b], y1 = b;
            }
        }
        for(int b = 0; b <= n; ++ b)
            if(vb[b])
                la[match[b]] -= delta, lb[b] += delta;
            else c[b] -= delta;
        y = y1;
    }while(match[y]);
    while(y)match[y] = match[p[y]], y = p[y];
}

ll KM()
{
    for(int i = 1; i <= n; ++ i)
        match[i] = la[i] = lb[i] = 0;
    for(int i = 1; i <= n; ++ i){
        for(int j = 1; j <= n; ++ j)
            vb[j] = false;
        bfs(i);
    }
    ll res = 0;
    for(int y = 1; y <= n; ++ y)
        res += w[match[y]][y];
    return res;
}

那么如果观察一下，发现其实这段代码于dfs版本有很多相像之处。

他有两个数组，c数组是这个过程中的差值，你会发现他一直在维护这个差值。而p数组记录的是前驱。

下面两个for循环基本与dfs相同，所以不做讲解。y1在这里记录了取得最小差值的点，就是要加入相等子图的这个点，如果它有匹配，那么我们就从这个点的匹配点开始。

至于最下面的那个while，我是这么理解的，因为我们一开始是从0开始的，所以我们挨个向上，让所有的匹配向下移一位，这是没有影响的，因为你目前为止记录到p中的所有点，经过访问这些点的所有的边在经过上述操作后都变成了相等子图上的边。

而为什么一开始的顶标标记没有符合我们的顶标建立标准，简单思考一下，你会发现其实这个问题无关紧要，因为如果这样，实际上delta到最后会取负值，然后在进行更新时，会自动的相当于我们手动为顶标赋值。

这是我的理解，实际上我对迭代算法的理解还不是很深刻，望有人能提供更好地想法。

5引用

1. 《算法竞赛进阶指南》
2. 他的博客

这篇关于KM + bfs迭代 算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！