Kuhn-Munkres Algorithm

 2020/05/10 

背景：带边权的二分图最大权值完美匹配。
顶标概念：顶点权值。
可行顶标：所有边，都满足。

注：此时还没有开始匹配，是对原图所有边的限制。
相等子图：包含所有顶点；仅包含的边。

问题即转化为求相等子图的完美匹配，此时边权和达到上限。
初始化：使得初始方案为可行顶标。
交替路：与匈牙利算法类似，在相等子图中搜索增广路时，如果找不到时我们称此时得到一条交替路。

如果将交替路中集合的顶标都，集合的顶标都，有以下结论：
- 如果在相等子图中，无变化，即该边仍在相等子图中。
- 如果不在相等子图中，当在交替路而不在交替路时，将减少，意味着该边有可能加入相等子图中。注意不能过大，否则会破坏可行顶标这个前提，因此 $在交替路不在交替路$
注：相等子图中顶标之和越来越小，以此来加入更多的边使得边权和更大。
代码模板

// find a perfect matching with maximum total cost
// in bipartite graph G=(X,Y;E).
// if you want the total cost minimum, just negative
// cost.
template<typename T>
struct KuhnMunkres {
	int n, m, vis[N], pre[N], mth[N];
	T INF, Lx[N], Ly[N], slack[N], w[N][N];

	void init(int _n, int _m, T _INF) {
		n = _n, m = _m, INF = _INF;
		// modify weight of non-edge if need
		rep(i, 0, n) rep(j, 0, m) w[i][j] = -INF;
	}

	inline void addEdge(int u, int v, int wgh) {
		w[u][v] = wgh;
	}

	void find(int v) {
		rep(i, 0, m + 1) vis[i] = 0, slack[i] = INF;
		int u = m;
		for (mth[u] = v; mth[u] != -1; u = v) {
			vis[u] = 1;
			T d = INF;
			rep(i, 0, m) if (!vis[i]) {
				T att = Lx[mth[u]] + Ly[i] - w[mth[u]][i];
				// maintain feasible solution
				if (att < slack[i]) slack[i] = att, pre[i] = u;
				// find minimum d
				if (slack[i] < d) d = slack[v = i];
			}
			rep(i, 0, m + 1)
				if (vis[i]) Lx[mth[i]] -= d, Ly[i] += d;
				else slack[i] -= d;
		}
		// find a augmented path
		for(; u != m; u = pre[u]) mth[u] = mth[pre[u]];
	}

	T solve() {
		bool iswap = false;
		if (n > m) {
			rep(i, 0, n) rep(j, 0, min(i, m))
				swap(w[i][j], w[j][i]);
			iswap = true, swap(n, m);
		}
		fill(Lx, Lx + n, 0);
		fill(Ly, Ly + m, 0);
		fill(mth, mth + m, -1);
		rep(i, 0, n) find(i);

		T ret = 0;
		rep(i, 0, n) ret += Lx[i];
		rep(i, 0, m) ret += Ly[i];
		if (iswap)
			per(i, 0, max(n, m)) swap(Lx[i], Ly[i]);
		return ret;
	}
};

原文作者：Mcginn

原文链接：http://mcginn7.github.io/2020/05/10/Kuhn-Munkres-Algorithm/

发表日期：May 10th 2020, 2:17:51 pm

更新日期：May 4th 2024, 5:07:17 pm

Next Post

SGU 153-252
Previous Post

CSAPP - cachelab

CATALOG