CF600F Edge coloring of bipartite graph

分享无脑选手神人做法。

注意到答案不小于最大度数

d

，猜测这就是答案，那么怎么构造呢。

最坏情况是每个点度数都是

d

，一般的情况都可以补全到这种情况：只需要把两边点数补到相等，然后补一些边使得度数正确即可。可以有重边。

现在问题变成把一个正则二分图划分成

d

组完美匹配。这是经典问题：如果

d

为偶数，可以找一组欧拉回路，然后递归到两个

\frac{d}{2}

的问题。如果

d

为奇数，那么每次随机一个点出发随机游走找增广路，可以证明这样会在

O(nd+n\log n)

的复杂度内找到一组匹配。总复杂度就是

O(nd \log d + nd \log n)

，不超过

O(n^2 \log n)

。

我使用该做法，在代码长度约为别人

3

倍且运行时间约为别人

6

倍的情况下通过了此题，可喜可贺。

CPP

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a, b, n, m;
struct Edge {
	int v, id;
	bool operator==(const Edge &b) const {
		return v == b.v && id == b.id;
	}
};
vector<Edge> e[2005];
struct EDat {
	int u, v, id;
};
EDat eP[1000005];
int epC;
int deg[2005], maxD, iC, cur[2005];
int pL[1000005], p[2005], pC;
bool vis[1000005];
void EDFS(vector<Edge> *e, int u) {
	for (int &i = cur[u]; i < e[u].size(); ) {
		auto ed = e[u][i++];
		if (vis[ed.id]) continue;
		vis[ed.id] = true;
		EDFS(e, ed.v);
		eP[++epC] = { ed.v, u, ed.id };
	}
}
mt19937 eng(363415);
int st[2005], top, mat[2005];
int cC, ans[100005];
void Solve(vector<Edge> *e) {
	if (e[1].size() & 1) {
		for (int i = 1; i <= n; i++) p[i] = i;
		for (int i = 1; i <= n * 2; i++) vis[i] = mat[i] = 0;
		shuffle(p + 1, p + n + 1, eng);
		for (int i = 1; i <= n; i++) {
			int u = p[i]; st[++top] = u;
			while (u) {
				int v;
				do v = e[u][eng() % e[u].size()].v; while (v == mat[u]);
				while (vis[v]) vis[st[top--]] = false;
				vis[st[++top] = v] = true;
				st[++top] = u = mat[v];
			}
			top--;
			for (int j = top; j; j -= 2) {
				int a = st[j], b = st[j - 1];
				mat[a] = b; mat[b] = a;
			}
			while (top) vis[st[top--]] = false;
		}
		cC++;
		for (int u = 1; u <= n; u++) {
			int v = mat[u], id = -1;
			for (auto [v, i] : e[u]) {
				if (v == mat[u]) {
					id = i; break;
				}
			}
			if (id <= m) ans[id] = cC;
			e[u].erase(find(e[u].begin(), e[u].end(), (Edge){ v, id }));
			e[v].erase(find(e[v].begin(), e[v].end(), (Edge){ u, id }));
		}
	}
	if (e[1].empty()) return;
	for (int i = 1; i <= n * 2; i++) cur[i] = 0;
	vector<Edge> eL[2005], eR[2005];
	for (int s = 1; s <= n * 2; s++) {
		if (cur[s] < e[s].size()) EDFS(e, s);
	}
	for (int i = 1; i <= n * 2; i++) {
		eL[i].reserve(e[1].size() / 2);
		eR[i].reserve(e[1].size() / 2);
	}
	for (int i = 1; i <= epC; i++) {
		auto [u, v, id] = eP[i];
		vis[id] = false;
		if (u <= n) eL[u].push_back({ v, id }), eL[v].push_back({ u, id });
		else eR[u].push_back({ v, id }), eR[v].push_back({ u, id });
	}
	epC = 0;
	Solve(eL), Solve(eR);
}
int main() {
	scanf("%d%d%d", &a, &b, &m), n = max(a, b);
	for (int i = 1, u, v; i <= m; i++) {
		scanf("%d%d", &u, &v);
		e[u].push_back({ v + n, i });
		deg[u]++, deg[v + n]++;
	}
	iC = m;
	for (int i = 1; i <= n * 2; i++) maxD = max(maxD, deg[i]);
	printf("%d\n", maxD);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= maxD - deg[i]; j++) pL[++pC] = i;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= maxD - deg[i + n]; j++) {
			e[pL[pC--]].push_back({ i + n, ++iC });
		}
	}
	for (int u = 1; u <= n; u++) {
		for (auto [v, id] : e[u]) e[v].push_back({ u, id });
	}
	Solve(e);
	for (int i = 1; i <= m; i++) printf("%d ", ans[i]);
	return 0;
}

CF600F Edge coloring of bipartite graph

文章操作

相关推荐

评论

CF600F Edge coloring of bipartite graph