KM算法简介

★ KM算法基本概念
（1）顶标：给定二分图左部第 i 个结点的值为 lx[i]，右部第 j 个结点的值为 ly[j]，结点 i 到结点 j 的边权为 w[i][j]，把满足 lx[i]+ly[j]≥w[i][j] 的整数值 lx[i] 及 ly[j]，称为结点的顶标。
（2）二分图的相等子图：二分图中所有结点及满足 lx[i]+ly[j]=w[i][j] 的边构成的子图，称为二分图的相等子图。
（3）匹配：在图论中，一个“匹配”是一个边的集合，其中任意两条边都没有公共顶点。
（4）最大匹配：一个图的所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。
（5）完备匹配：若二分图的某个匹配中，所有的顶点都是匹配点，那么这个匹配就是一个完备匹配。若相等子图中存在完备匹配，则这个完备匹配就是二分图的带权最大匹配。
（6）交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边、……，形成的路径叫交替路。
（7）增广路：从一个未匹配点出发，走交替路，如果途经另一个未匹配点（出发点不算），则这条交替路称为增广路（agumenting path）。

★ KM算法的基本思想
对任意 i，j， 在满足 lx[i]+ly[j]≥w[i][j] 的前提下，给每个结点随意赋值一个顶标， 然后采取适当策略不断扩大相等子图的规模，直至相等子图存在完备匹配。
Kuhn－Munkres算法流程：
（1）初始化可行顶标的值。通常，lx[i] 取输入各值的最大值，ly[j] 取 0。
（2）用匈牙利算法寻找完备匹配；
（3）若未找到完备匹配则修改可行顶标的值；
（4）重复（2）和（3），直到找到相等子图的完备匹配为止。

《奔小康赚大钱》之C++代码实现KM算法

#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

const int inf=0x3f3f3f3f;
const int maxn=305;
int mp[maxn][maxn]; //Graph
int lx[maxn],ly[maxn]; //topmark x, topmark y
int match[maxn],slack[maxn];
bool visx[maxn],visy[maxn];
int n;

bool find(int x) {
    visx[x]=1;
    for(int y=0; y<n; y++) {
        if(visy[y]) continue;
        int t=lx[x]+ly[y]-mp[x][y];
        if(t==0) {
            visy[y]=1;
            if(match[y]==inf || find(match[y])) {
                match[y]=x;
                return true;
            }
        } else slack[y]=min(t,slack[y]);
    }
    return false;
}

int KM() {
    memset(ly,0,sizeof(ly));
    memset(match,inf,sizeof(match));

    for(int i=0; i<n; i++) {
        memset(slack,inf,sizeof(slack));
        while(1) {
            memset(visx,0,sizeof(visx));
            memset(visy,0,sizeof(visy));
            if(find(i)) break; //match

            int d=inf;
            for(int i=0; i<n; i++)
                if(!visy[i]) d=min(d,slack[i]);

            //The left topmarks in the match are all decremented by d.
            for(int i=0; i<n; i++)
                if(visx[i]) lx[i]-=d;

            //The right topmarks in the match are all incremented by d.
            //Otherwise, reduce the slack.
            for(int i=0; i<n; i++)
                if(visy[i]) ly[i]+=d;
                else slack[i]-=d;
        }
    }

    int ans=0;
    for(int i=0; i<n; i++)
        if(match[i]!=inf) ans+=mp[match[i]][i];

    return ans;
}

int main() {
    while(cin>>n) {
        memset(lx,0,sizeof(lx));
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++) {
                cin>>mp[i][j];
                if(mp[i][j]>lx[i]) lx[i]=mp[i][j];
            }

        cout<<KM()<<endl;
    }

    return 0;
}

/*
in:
2
100 10
15 23

out:
123
*/