KM(Kuhn-Munkres)算法

带权二分图最佳完美匹配，O(n^3)，（运用匈牙利算法辅助求解），同时也是完备匹配

只适用于带权最大匹配一定是完备匹配的情况，实践中建议用费用流来解决。
完全二分图一定是偶数个点
可行顶标（Feasible Labeling）：结点函数（x），任意边（x，y）：1（x）+l（y）≥w（xiy）。
相等子图：G的生成子图，包含所有点以及满足l（x）+I（y）=w（x，y）的边（x，y）
如果EL有完美匹配为PM，则该M是原图的最大权匹配：
- PM的权和等于所有点的顶标之和SV。
- G的任一个最大权匹配M，边满足w（xy）≤l（x）+（y）→M边权和≤SV=PM边权和
- 关键就是寻找好的可行顶标，使相等子图有完美匹配。

==>找到原图的完美匹配–只要–>找到相等子图的完美匹配即可

▲KM完成之后所有的l(x)之和最小

执行过程

一般对KM算法的描述，基本上可以概括成以下几个步骤：
1.用邻接矩阵（或其他方法也行啦）来储存图。
2.运用贪心算法初始化标杆。
3.运用匈牙利算法找到完备匹配。
4.如果找不到，则通过修改标杆，增加一些边。
5.重复3，4的步骤，直到完全匹配时可结束。

二分图匹配里面我们找最大边进行连边!但是遇到某个点被匹配了两次怎么办？
那就用匈牙利算法进行更改匹配！

这就是KM算法的思路了：尽量找最大的边进行连边，如果不能则换一条较大的。

找对象例子理解重点：

女生的每轮选择都是从第一个男生开始往后选择一个男生，使男女两人的期望和要等于两人之间的好感度。
注意：每一轮匹配，每个男生只会被尝试匹配一次！
如果找对象失败，那么此时参与匹配过的女生期望值都降低d，本轮被选择的男生期望值都增加d：d为任意一个这轮参与过匹配的女生能换到***任意一个这轮没有被选择过的男生所需要降低的最小值*（遍历左边已配对的X，标杆值Lx，与右边这一轮没被选择过的男生Y，标杆值Ly，挑出需要降低的最小值，即 d=min(Lx+Ly-W, d) ）

复杂度

朴素的实现方法，时间复杂度为O(n4)——需要找O(n)次增广路，每次增广最多需要修改O(n)次顶标，每次修改顶标时由于要枚举边来求d值，复杂度为O(n2)。

实际上KM算法的复杂度是可以做到O(n3) 的。我们给每个Y顶点一个“松弛量”函数slack，每次开始找增广路时初始化为无穷大。在寻找增广路的过程中，检查边(i,j)时，如果它不在相等子图中，则让slack[j]变成原值与A[i]+B[j]-w[i,j]的较小值。这样，在修改顶标时，取所有不在交错树中的Y顶点的slack值中的最小值作为d值即可。但还要注意一点：修改顶标后，要把所有的slack值都减去d。（即用在执行匈牙利算法的时候，进行对slack的更新，从而减少一层找到最小d的循环）

举个栗子:

少林决胜(Golden Tiger Claw，UVa11383)

给定一个N*N矩阵，每个格子里都有一个正整数w(i,j)。你的任务是给每行确定一个整数row(i)，每列也确定一个整数col(i)，使得对于任意格子(i, j)，w(i, j)≤row(i)+colj)。所有row(i)和col(i)之和应尽量小。

【分析】
1.行看作二分图X点，列看作二分图Y点。
2.和最佳匹配没有任何关系，KM算法副产品。
3.KM中算法等式l（x）+l（y）≥w（x，y）。行X，列Y。
4.KM过程中，所有顶标不断减小，算法结束后，所有顶标之和是最小的。

蚂蚁（Ants，NEERC2008，LA4043）

给出n个白点和n个黑点的坐标，要求用n条不相交的线段把它们连接起来，其中每条线段恰好连接一个白点和一个黑点，每个点恰好连接到一条线段，如图所示。

【分析】

点有黑白两色，构造二分图，白X黑Y。每个黑点和每个白点相连，权值等于欧氏距离。
连接方案实际上是计算一个完美匹配，匹配中假设al-b1与a2-b2相交，那么dist(a1，b1)+dist(a2，b2)>dist(al，b2)+dist(a2，b1)，这两条线段改成al-b2和a2-b1后总长度会变少。
所以最小匹配中不会出现线段相交。
套KM算法即可计算最小完美匹配即可。

附录

O(n^3)代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <ctime>
using namespace std;
const int MAXN = 305;
const int INF = 0x3f3f3f3f;

// X为女生节点， Y为男生节点
int love[MAXN][MAXN];   // 记录每个妹子和每个男生的好感度

int ex_girl[MAXN];      // 每个妹子的期望值
int ex_boy[MAXN];       // 每个男生的期望值
bool vis_girl[MAXN];    // 记录每一轮匹配匹配过的女生
bool vis_boy[MAXN];     // 记录每一轮匹配匹配过的男生
int match[MAXN];        // 记录每个男生匹配到的妹子 如果没有则为-1
int slack[MAXN];        // 记录每个汉子如果能被妹子倾心最少还需要多少期望值

int N;


bool dfs(int girl){
    vis_girl[girl] = true;

    for (int boy = 0; boy < N; ++boy) {

        if (vis_boy[boy]) continue; // 每一轮匹配 每个男生只尝试一次

        int gap = ex_girl[girl] + ex_boy[boy] - love[girl][boy];

        if (gap == 0) {  // 如果符合要求
            vis_boy[boy] = true;
            if (match[boy] == -1 || dfs( match[boy] )) {    // 找到一个没有匹配的男生 或者该男生的妹子可以找到其他人
                match[boy] = girl;
                return true;
            }
        } else {
            slack[boy] = min(slack[boy], gap);  // slack 可以理解为该男生要得到女生的倾心 还需多少期望值 取最小值 备胎的样子【捂脸
        }
    }

    return false;
}

int KM(){
    // ▲初始化有关被选择的男生的量1-2 [选择他的女生、男生方标杆]
    memset(match, -1, sizeof match);    // 初始每个男生都没有匹配的女生
    memset(ex_boy, 0, sizeof ex_boy);   // 初始每个男生的期望值为0

    // ▲初始化3 [女生方的标杆]
    // 每个女生的初始期望值是与她相连的男生最大的好感度
    for (int i = 0; i < N; ++i) {
        ex_girl[i] = love[i][0];
        for (int j = 1; j < N; ++j) {
            ex_girl[i] = max(ex_girl[i], love[i][j]);
        }
    }

    // 尝试为每一个女生解决归宿问题
    for (int i = 0; i < N; ++i) {

        // ▲初始化4 [slack-找到最小的d]
        fill(slack, slack + N, INF);    // 因为要取最小值 初始化为无穷大

        while (1) {
            // 为每个女生解决归宿问题的方法是 ：如果找不到就降低期望值，直到找到为止

            // 初始化5-6 [该轮中那些女生已经尝试匹配过，该轮中那些男生被选择过]
            // 记录每轮匹配中男生女生是否被尝试匹配过
            memset(vis_girl, false, sizeof vis_girl);
            memset(vis_boy, false, sizeof vis_boy);

            if (dfs(i)) break;  // 找到归宿 退出

            // 如果不能找到 就降低期望值
            // 最小可降低的期望值
            int d = INF;
            for (int j = 0; j < N; ++j)
                if (!vis_boy[j]) d = min(d, slack[j]);

            for (int j = 0; j < N; ++j) {
                // 所有访问过的女生降低期望值
                if (vis_girl[j]) ex_girl[j] -= d;

                // 所有访问过的男生增加期望值
                if (vis_boy[j]) ex_boy[j] += d;
                // 没有访问过的boy 因为girl们的期望值降低，距离得到女生倾心又进了一步！
                else slack[j] -= d;
            }
        }
    }

    // 匹配完成 求出所有配对的好感度的和
    int res = 0;
    for (int i = 0; i < N; ++i)
        res += love[ match[i] ][i];

    return res;
}

int main(){
    while (~scanf("%d", &N)) {
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N; ++j)
                scanf("%d", &love[i][j]);
        printf("%d\n", KM());
    }


    return 0;
}

裸题:HDU2255 奔小康赚大钱
输入数据包含多组测试用例，每组数据的第一行输入n,表示房子的数量(也是老百姓家的数量)，接下来有n行,每行n个数表示第i个村名对第j间房出的价格(n<=300)。

Sample Input
2		// 一共有两个房子
100 10	// 村民1对第一间出价100, 第二间10
15 23   // 村民1对第一间出价15, 第二间23
Sample Output
123		// 第一间给1,第二间给2

获得其他数据：

int main(){
    N = 3;
    srand(time(0));
    for (int i = 0; i < N; ++i){
        for (int j = 0; j < N; ++j){
            int tmp = rand() % 3*N + 1;
            love[i][j] = tmp;
            printf("%d ", love[i][j] );
        }
        printf("\n");
    }
    printf("%d\n", KM());
    int sum = 0;
    for (int i = 0; i < N; ++i){
        printf("%d->%d\n", match[i], i);
        sum += love[match[i]][i];
    }
    printf("和最大：%d\n", sum);

    for (int i = 0; i < N; ++i){
        for (int j = 0; j < N; ++j){
            love[i][j] = -love[i][j] ;
            printf("%d ", love[i][j] );
        }
        printf("\n");
    }
    printf("和最小：%d\n", -KM());
    sum = 0;
    for (int i = 0; i < N; ++i){
        printf("%d->%d\n", match[i], i);
        sum += love[match[i]][i];
    }
    printf("%d\n", sum);
    return 0;
}
/**
4 1 7 
1 4 7 
1 7 4 
18
0->0
2->1
1->2
18
-4 -1 -7 
-1 -4 -7 
-1 -7 -4 
6
1->0
0->1
2->2
-6
*/

参考资料：

二分图匹配之最佳匹配——KM算法

KM算法详解+模板——男女相亲匹配

带你入门多目标跟踪（三）匈牙利算法&KM算法——以图像目标跟踪距离