AcWing 404. 婚礼

大型补档计划

根据题意，显然只有新郎这边可能存在矛盾，考虑这边怎么放即可，新娘那边的放法与这边正好相反且一一对应。

显然对于两个约束条件是一对矛盾，开始我以为可以用并查集，后来发现输出方案的时候，如果两者都可以的话不会选了只能乱选，有可能会限制死某些变量，需要指数级别 \(dfs\) 搞，然后就放弃了。

设 \([0, n - 1]\) 是这个位置放妻子，\([n, 2 * n - 1]\) 是这个位置放丈夫。

对于这种矛盾 \(a, b\)，构建 2-SAT 模型就是连边 \((a, opp[b]), (b, opp[a])\) （opp表示同样位置的对应元素。）

方案输出按照板子输出即可，注意输出的是新娘一边的，正好我们求的新郎正相反

#include <cstdio>

#include <iostream>

#include <cstring>

using namespace std;

const int N = 65, M = 2005;

int n, m, dfn[N], low[N], dfncnt, s[N], top, c[N], cnt;

bool ins[N];

int opp(int x) { return x <= n - 1 ? x + n : x - n; }

int head[N], numE = 0;

struct E{

	int next, v;

} e[M];

void add(int u, int v) {

	e[++numE] = (E) { head[u], v };

	head[u] = numE;

}

void tarjan(int u) {

	dfn[u] = low[u] = ++dfncnt;

	ins[u] = true, s[++top] = u;

	for (int i = head[u]; i; i = e[i].next) {

		int v = e[i].v;

		if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);

		else if(ins[v]) low[u] = min(low[u], dfn[v]);

	}

	if (dfn[u] == low[u]) {

		int v; ++cnt;

		do {

			v = s[top--], c[v] = cnt, ins[v] = false;

		} while (v != u);

	}

}

void clear() {

	memset(dfn, 0, sizeof dfn);

	memset(head, 0, sizeof head);

	memset(c, 0, sizeof c);

	memset(ins, false, sizeof ins);

	numE = dfncnt = top = cnt = 0;

}

bool check() {

	for (int i = 0; i <= n - 1; i++) if (c[i] == c[i + n]) return false;

	return true;

}

int main() {

	while(scanf("%d%d", &n, &m), n || m) {

		clear();

		add(0, n);

		for (int i = 1, x, y; i <= m; i++) {

			char a, b; scanf("%d%c%d%c", &x, &a, &y, &b);

			if (a == 'h') x += n;

			if (b == 'h') y += n;

			add(x, opp(y)), add(y, opp(x));

		}

		for (int i = 0; i <= 2 * n - 1; i ++) if (!dfn[i]) tarjan(i);

		if (!check()) puts("bad luck");

		else {

			for (int i = 1; i <= n - 1; i++)  printf("%d%c ", i, c[i] < c[i + n] ? 'h' : 'w');

			puts("");

		}

	}

}

巴特西

AcWing 404. 婚礼

最新文章

热门文章