「Note」KM

便于记忆。。。

using namespace std;
const int MAXN = 505;
const int INF = 0x3f3f3f3f;

int n, m, la[MAXN], lb[MAXN], sl[MAXN], match[MAXN], w[MAXN][MAXN], fa[MAXN], ans, re[MAXN];
bool vis[MAXN];

void bfs(int u) {
	memset(sl, 0x3f, sizeof(sl)); // 将 slack 标记清空
	memset(vis, 0, sizeof(vis)); // 清 vis

	int pos = 0, x, p, delta;

	for (match[pos] = u; match[pos]; pos = p) { // 迭代模拟递归

		vis[pos] = 1, x = match[pos], delta = INF; // 初始化 置标记,从右部图节点到匹配的左部图,把 delta 置为无穷
		for (int y = 1; y <= n; y++) { // 遍历右部的节点
			if (vis[y]) continue;
			if (la[x] + lb[y] - w[x][y] < sl[y]) { // 更新 sl 标记
				sl[y] = la[x] + lb[y] - w[x][y];
				fa[y] = pos; // 记录前驱
			} 
			if (sl[y] < delta) {
				delta = sl[y]; // 更新 delta
				p = y; // 把 y 丢进去扩展 相当于 dfs(y)
			}
		} 

		for (int y = 0; y <= n; y++) {
			if (vis[y]) la[match[y]] -= delta, lb[y] += delta; // 把经过的顶点权值更新
			else sl[y] -= delta; // 更新 slack 此处可以消掉一个 n
		}

	}

	for (; pos; pos = fa[pos]) match[pos] = match[fa[pos]]; // 增广重置匹配

}

void KM() { for (int i = 1; i <= n; i++) bfs(i); }

整个算法的时间复杂度是 $\mathcal{O(n ^ 3)}$