526互联

AtCoder Regular Contest 161 E Not Dyed by Majority (Cubic Graph)

发布时间 2023-05-29 08:54:26作者: zltzlt

洛谷传送门

AtCoder 传送门

给构造题提供了一种新的思路。

如果答案占总方案数的比较大，可以考虑随机化。

例如本题，考虑随机化，难点变成判断一个方案是否可行。考虑 2-SAT，如果一个点是 \(\text{B}\)，那么对于这个点的边，有一条边的另一个端点是 \(\text{W}\)，那么其他两个都是 \(\text{B}\)。反之同理。跑一遍 2-SAT 即可知道随出来的这个解是否合法。

code 
// Problem: E - Not Dyed by Majority (Cubic Graph)
// Contest: AtCoder - AtCoder Regular Contest 161
// URL: https://atcoder.jp/contests/arc161/tasks/arc161_e
// Memory Limit: 1024 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;

const int maxn = 500100;

int n, f[maxn], head[maxn], len;
vector<int> G[maxn];
mt19937 rnd(time(NULL));
int dfn[maxn], low[maxn], times, scc[maxn], cnt, stk[maxn], top;
struct edge {
	int to, next;
} edges[maxn * 10];

inline void add_edge(int u, int v) {
	edges[++len].to = v;
	edges[len].next = head[u];
	head[u] = len;
}

void dfs(int u) {
	dfn[u] = low[u] = ++times;
	stk[++top] = u;
	for (int i = head[u]; i; i = edges[i].next) {
		int v = edges[i].to;
		if (!dfn[v]) {
			dfs(v);
			low[u] = min(low[u], low[v]);
		} else if (!scc[v]) {
			low[u] = min(low[u], dfn[v]);
		}
	}
	if (dfn[u] == low[u]) {
		++cnt;
		while (1) {
			int x = stk[top--];
			scc[x] = cnt;
			if (x == u) {
				break;
			}
		}
	}
}

void solve() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		vector<int>().swap(G[i]);
	}
	for (int i = 0, u, v; i < n * 3 / 2; ++i) {
		scanf("%d%d", &u, &v);
		G[u].pb(v);
		G[v].pb(u);
	}
	while (1) {
		for (int i = 1; i <= n; ++i) {
			f[i] = rnd() & 1;
		}
		len = times = cnt = 0;
		for (int i = 1; i <= n * 2; ++i) {
			head[i] = dfn[i] = low[i] = scc[i] = 0;
		}
		for (int i = 1; i <= n; ++i) {
			int u = G[i][0], v = G[i][1], w = G[i][2];
			if (f[i]) {
				add_edge(u, v + n);
				add_edge(u, w + n);
				add_edge(v, u + n);
				add_edge(v, w + n);
				add_edge(w, u + n);
				add_edge(w, v + n);
			} else {
				add_edge(u + n, v);
				add_edge(u + n, w);
				add_edge(v + n, u);
				add_edge(v + n, w);
				add_edge(w + n, u);
				add_edge(w + n, v);
			}
		}
		for (int i = 1; i <= n * 2; ++i) {
			if (!dfn[i]) {
				dfs(i);
			}
		}
		bool flag = 0;
		for (int i = 1; i <= n; ++i) {
			if (scc[i] == scc[i + n]) {
				for (int u = 1; u <= n; ++u) {
					putchar(f[u] ? 'B' : 'W');
				}
				putchar('\n');
				flag = 1;
				break;
			}
		}
		if (flag) {
			break;
		}
	}
}

int main() {
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}