KM算法学习 (二分图带权最大匹配)

计算 二分图带权最大匹配的2种方法: 费用流 / KM

KM算法学习

1. 使用局限性:只能在带权最大匹配是完备匹配的图中使用

   • 完备匹配: G=<V1,V2,E>为二分图,$|V_1| < |V_2|$,$M$为$G$中的一个最大匹配数,且$|M|= |V_1|$,则称$M$为$V_1$到$V_2$的完备匹配
   • 完美匹配:当$|V_1| = |V_2|$,若$|V_1|<|V_2|$,则完备匹配为$G$中的最大匹配

   ---

2. KM算法准备条件

   1. 顶标(顶点标记值),给定第$i (1<=i<=N)$个 左部节点一个整数值$A_i$,给定第$j (1<=j<=N)$个右部节点一个整数值$B_j$, 必须满足$\forall i,j, A_i+B_j \geq w(i,j)$,$w(i,j)$表示i,j之间的边权( 无 边 设 为 负 无 穷 )

   2. 相等子图,二分图中 所有满足$A_i+B_j = w(i,j)$的边构成的子图

      若相等子图有完备匹配,那么就是带权最大匹配

   3. 交错树.左部分的点匹配不成功时dfs访问过的点和边组成的树

3. KM算法流程

   1. 初始化$A_i = max_{1\leq j \leq N}{w(i,j)}$(点的所有出边的中的边的值)，$B_j=0$

   2. dfs过程中记录$K = min{A_i+B_j-w(i,j)}$，如果把交错树中左部顶点的顶标全都减小K,右部顶点的顶标增加K:

      1. 两端都在交错树的边$(i,j)$ ，$A_i+B_j$没有变化,仍然属于原来相等子图
      2. 两端都不在交错树的边$(i,j)$，$A_i+B_j$都没变化,仍然不属于原来相等子图
      3. 左端不在右端在交错树的边$(i,j)$，$A_i+B_j$变大,原来不属于,现在更不可能属于
      4. 左端在而右端不在交错树的边$(i,j)$，$A_i+B_j$变小,原来不在,现在可能进入相等子图中,使得相等子图变大,

   3. 未找到该点的完备匹配通过上一步修改顶标值一直找下去

例题POJ 2195

• 要求的是最小权值的完美匹配,将权值转成负值使用KM算法得到最大权值和换成正数也就是最小

#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <utility>

using namespace std;
const int maxn = 110;
const int N = 1e4;

int w[maxn][maxn],la[maxn],lb[maxn],match[maxn];
bool va[maxn],vb[maxn];
int n,delta,m,cnt;
int house_size,man_size;

struct node {
    int x,y;
}house[N],man[N];
//vector<node> house,man;

int distance1(node a,node b) {
    return abs(a.x - b.x) + abs(a.y - b.y);
}

int dfs(int x) {
    va[x] = 1;
    for (int y=1; y<=house_size; ++y) {
        if (!vb[y])
            if (la[x] + lb[y] - w[x][y] == 0) {
                vb[y] = 1;
                if (!match[y] || dfs(match[y])) {
                    match[y] = x;
                    return 1;
                }
            }
            else delta = min(delta,la[x]+lb[y]-w[x][y]);
    }
    return 0;
}

int KM() {
    for (int i=1; i<=man_size; ++i)
        for (int j=1; j<=house_size; ++j)
            la[i] = max(la[i],w[i][j]);
    for (int i=1; i<=man_size; ++i)
        while (1) {
            memset(va,0,sizeof va);
            memset(vb,0,sizeof vb);
            delta = 1 << 30;
            if (dfs(i)) break;
            for (int i=1; i<=man_size; ++i) {
                if (va[i]) la[i] -= delta;
                if (vb[i]) lb[i] += delta;
            }
        }
    int ans = 0;
    for (int i=1; i<=house_size; ++i) ans += w[match[i]][i];
    return ans;
}

void init() {
    house_size= man_size =0;

    delta = 0x3f3f3f3f;
    memset(w,0,sizeof w);
    memset(lb,0,sizeof lb);
    memset(match,0,sizeof match);

    for (int i=1; i<=maxn; ++i)
        la[i] = -0x3f3f3f3f;
}

void read() {
    for (int i=1; i<=cnt; ++i) {
        for (int j=1; j<=m; ++j) {
            char ch = getchar();
            if (ch == 'H') {
                //house.push_back(node(i,j));
                house[house_size].x=i;
                house[house_size++].y=j;
            }
            else if (ch == 'm') {
                //man.push_back(node(i,j));
                man[man_size].x = i;
                man[man_size++].y=j;
            }
        }
        getchar();
    }
    for (int i=0; i<man_size; ++i)
        for (int j=0; j<house_size; ++j)
            w[i+1][j+1] = -distance1(man[i],house[j]);
}

int main() {
    freopen("1.in","r",stdin);
    while (scanf("%d %d\n",&cnt,&m) && cnt && m) {
        init();
        read();
        cout << -KM() << endl;
    }
    return 0;
}