Location>code7788 >text

Bipartite graph maximum power perfect matching

Popularity：273 ℃/2024-09-19 11:41:13

concern

Given a bipartite graph, the left part has\(n\) points, with the right part of the\(m\) Points, Edges\((u_i, v_j)\) The edge weights of the\(A_{i,j}\). Find the perfect matching of the maximum weight of this bipartite graph.

isomerization (chemistry)

The problem can be written in the form of a linear program, letting\(f_{i, j}\) Indicates if there is an edge in the match\((u_i, v_j)\)seek

\[\begin{gather*} \text{maximize} \quad & \sum_{i=1}^n \sum_{j=1}^m f_{i, j} \times A_{i, j} \\ \text{subject to} \quad & \sum_{i=1}^n f_{i, j} = 1 \quad \forall j \in [1, m] \\ & \sum_{j=1}^m f_{i,j}=1\quad\forall i \in [1, n] \\ & f_{i,j} \ge 0 \quad\forall i, j \end{gather*} \]

Turning to the dyadic problem:

\[\begin{gather*} \text{minimize} \quad & \sum_{i=1}^n hu_i + \sum_{j=1}^m hv_i \\ \text{subject to} \quad & hu_i + hv_i \ge A_{i,j} \quad\forall i, j \end{gather*} \]

In this issue.\(hu\) cap (a poem)\(hv\) Also known as "top mark".

analyze

By the complementary relaxation theorem, if\(f_{i,j}=1\)then there are\(hu_i+hv_j=A_{i,j}\). This gives a way to determine whether a set of vertices is optimal or not:

A set of top marks\(hu, hv\) is optimal if and only if the subgraph\(H = \left\{(i, j) \mid hu_i + hv_j = A_{i,j}\right\}\) A perfect match exists.

practice

It is first given that a program that satisfies\(hu_i+hv_j \ge A_{i,j}\) (not necessarily optimal) (e.g., so that\(hu_i = hv_j = +\infty\)) and maintains the corresponding matches. Then try to modify the superscript without breaking the condition so that the match can be augmented.

Specifically, traversing\(i\) through (a gap)\(1\) until (a time)\(n\)Each time you try to put\(i\) added to the matching (similar to the Hungarian algorithm for finding the maximum match of a bipartite graph). We can solve for thein order to\(i\) get atIf there is already a generalization path, then it is straightforward to generalize it, otherwise we need to modify the vertices to make the interleaved tree grow. Let the set of points in the left part of the staggered tree be\(S\)and the right point set is\(T\)Then there must be\(|S| = |T| + 1\)(Properties of interleaved trees). Let\(\Delta = \min\{hu_i + hv_j - A_{i,j} \mid i \in S \land j \notin T\}\)Then it will be\(S\) The point vertices in the\(\Delta\)will\(T\) The point vertices in the\(\Delta\), it can be verified that the resulting new superscript still satisfies\(hu_i+hv_j \ge A_{i,j}\) restrictions, and the matches in the original graph must be contained in the corresponding new graphs\(H'\) In addition, at least one edge has been added to the new graph, which allows our interleaved tree to continue to grow until we find the augmentation path.

Code (Rock Valley P6577）

#define DEBUG 0
#include <cstdio>
#include <cassert>
#include <vector>
template <class T> using Arr = std::vector<T>;
#define int long long
const int INF = 1e8;

signed main() {
	int n, m;
	scanf("%lld%lld", &n, &m);
	struct edge_t {
		int v, w;
	};
	Arr<Arr<edge_t>> e(2 * n);
	for (int i = 0; i < m; ++i) {
		int l, r, w;
		scanf("%lld%lld%lld", &l, &r, &w);
		--l; r += n - 1;
		e[l].push_back({r, w});
		e[r].push_back({l, w});
	}

	Arr<int> match(2 * n, -1), h(2 * n, INF);
	for (int i = 0; i < n; ++i) {
		Arr<int> vis(2 * n, false); // Is it in the current interleaved tree?，assume (office) $S \cup T$
		Arr<int> upd(2 * n, n * INF); // smallest Δ (be) worth
		Arr<int> from(2 * n, -1); // Maintenance of Zeng Guang Road，assume (office)交错树上的父亲
		int p = i;
		vis[p] = true;
		int d, dp; // Δ and its corresponding j
		while (true) {
			d = n * INF, dp = -1;

			// work out Δ
			for (auto [to, w] : e[p])
				if (!vis[to]) {
					int delta = h[p] + h[to] - w;
					if (delta < upd[to])
						upd[to] = delta, from[to] = p;
				}
			for (int j = n; j < 2 * n; ++j)
				if (!vis[j] && upd[j] < d && from[j] != -1)
					d = upd[j], dp = j;
			assert(~dp);


			// Modify the top label
			h[i] -= d;
			for (int j = n; j < 2 * n; ++j)
				if (vis[j])
					h[j] += d, h[match[j]] -= d;
				else
					upd[j] -= d;

			// Find Zeng Guang Road
			if (match[dp] == -1)
				break;

			// alternate phyllotaxy (botany)
			vis[dp] = true;
			vis[match[dp]] = true;
			p = match[dp];
		}

		// widen
		while (~dp) {
			match[dp] = from[dp];
			int tmp = match[from[dp]];
			match[from[dp]] = dp;
			dp = tmp;
		}
	}

	long long ans = 0;
	for (int i = 0; i < 2 * n; ++i)
		ans += h[i];
	printf("%lld\n", ans);
	for (int i = n; i < 2 * n; ++i)
		printf("%lld ", match[i] + 1);
	puts("");
	return 0;
}

bibliography

  • /graph/
  • /blog/entry/128703
<Previous Next>