首先直观理解匈牙利算法：
趣写算法系列之--匈牙利算法:https://blog.csdn.net/dark_scope/article/details/8880547(已转载）
然后进入KM算法：
带权二分图的最佳匹配（KM算法）：https://blog.csdn.net/x_y_q_/article/details/51927054（已转载）
步骤：
其中S表示交错路中X的顶点，T表示交错路中Y顶点。
模板：
其中匈牙利匹配的理解:
当到达x4时，x4会尝试匹配y2，对应y2被标记为true。y2被x3占用，此时会回溯查找x3可否更改顶点，发现x3和y3连接，对应y3被标记为true。y3被x1占用，此时会回溯查找x1可否更改顶点，发现x1没办法继续更改（因为y2和y3均为true，被标记）。
x4会继续尝试匹配y3，此时发现y3之前已经标记，不再回溯。这里很重要！本质上，S = {x1，x2，x3}是没有完美匹配的，因为S的邻点集N(S)={y2，y3}，数目小于S中顶点数，第一次x4尝试匹配y2的时候已经发现这个问题。所以如果x4下一次尝试匹配的点仍在y2和y3中时，肯定没有完美匹配，所以不需要回溯。
//test case://5//3 5 5 4 1//2 2 0 2 2//2 4 4 1 0//0 1 1 0 0//1 2 1 3 3//14#include <iostream>#include <cstdio>#include <memory.h>#include <algorithm> using namespace std;#define MAX 100int n;int weight[MAX][MAX]; //权重int lx[MAX], ly[MAX]; //定点标号bool sx[MAX], sy[MAX]; //记录寻找增广路时点集x，y里的点是否搜索过int match[MAX]; //match[i]记录y[i]与x[match[i]]相对应bool search_path(int u) { //给x[u]找匹配,这个过程和匈牙利匹配是一样的sx[u] = true;for (int v = 0; v < n; v++) {if (!sy[v] && lx[u] + ly[v] == weight[u][v]) {sy[v] = true;if (match[v] == -1 || search_path(match[v])) {match[v] = u;return true;}}}return false;}int Kuhn_Munkras(bool max_weight) {if (!max_weight) { //如果求最小匹配，则要将边权取反for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)weight[i][j] = -weight[i][j];}//初始化顶标，lx[i]设置为max(weight[i][j] | j=0,..,n-1 ), ly[i]=0;for (int i = 0; i < n; i++) {ly[i] = 0;lx[i] = -0x3f3f3f3f;for (int j = 0; j < n; j++)if (lx[i] < weight[i][j])lx[i] = weight[i][j];}memset(match, -1, sizeof(match));//不断修改顶标，直到找到完备匹配或完美匹配for (int u = 0; u < n; u++) { //为x里的每一个点找匹配while (1) {memset(sx, 0, sizeof(sx));memset(sy, 0, sizeof(sy));if (search_path(u)) //x[u]在相等子图找到了匹配,继续为下一个点找匹配break;//如果在相等子图里没有找到匹配，就修改顶标，直到找到匹配为止//首先找到修改顶标时的增量inc, min(lx[i] + ly [i] - weight[i][j],inc);//lx[i]为搜索过的点，ly[i]是未搜索过的点,因为现在是要给u找匹配，所以只需要修改找的过程中搜索过的点，增加有可能对u有帮助的边int inc = 0x3f3f3f3f;//根据公式，交错路上的X减去min(lx[i] + ly[j] - weight[i][j]);交错路上的Y减去min(lx[i] + ly[j] - weight[i][j])for (int i = 0; i < n; i++)if (sx[i])for (int j = 0; j < n; j++)if (!sy[j] && ((lx[i] + ly[j] - weight[i][j]) < inc))inc = lx[i] + ly[j] - weight[i][j];//找到增量后修改顶标，因为sx[i]与sy[j]都为真，则必然符合lx[i] + ly [j] =weight[i][j]，然后将lx[i]减inc，ly[j]加inc不会改变等式，//但是原来lx[i] + ly [j] ！=weight[i][j]即sx[i]与sy[j]最多一个为真，lx[i] + ly [j] 就会发生改变，从而符合等式，边也就加入到相等子图中if (inc == 0x3f3f3f3f){cout << "no perfect match!" << endl;return 0;}for (int i = 0; i < n; i++) {if (sx[i]) //lx[i] -= inc;if (sy[i])ly[i] += inc;}}}int sum = 0;for (int i = 0; i < n; i++)if (match[i] >= 0)sum += weight[match[i]][i];if (!max_weight)sum = -sum;return sum;}int main() {scanf_s("%d", &n);for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)scanf_s("%d", &weight[i][j]);printf("%dn", Kuhn_Munkras(1));//默认最大匹配。若是最小，把1改为0system("pause");return 0;}