【hihoCoder 第133周】2-SAT·hihoCoder音乐节

http://hihocoder.com/problemset/problem/1467

2-sat模板。。。详细的题解请看题目里的提示。

tarjan模板打错again致命伤qwq

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = 103;

const int M = 1003;

bool inst[N << 1];

struct node {int nxt, to;} E[M << 1];

int cnt, point[N << 1], dfn[N << 1], low[N << 1], st[N << 1], top = 0, bel[N << 1];

void ins(int u, int v) {E[++cnt] = (node) {point[u], v}; point[u] = cnt;}

char A[23], B[23];

int n, m, a, b, ct, tot;

void tarjan(int x) {

	dfn[x] = low[x] = ++ct;

	inst[st[++top] = x] = true;

	for (int i = point[x], v = E[i].to; i; v = E[i = E[i].nxt].to)

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

		else if (inst[v]) low[x] = min(low[x], dfn[v]);

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

		++tot;

		while (st[top] != x) {

			inst[st[top]] = false;

			bel[st[top--]] = tot;

		}

		inst[x] = false;

		bel[st[top--]] = tot;

	}

}

int main() {

	int T; scanf("%d", &T);

	while (T--) {

		scanf("%d%d", &n, &m);

		int doublen = n << 1;

		memset(point, 0, sizeof(int) * doublen);

		memset(dfn, 0, sizeof(int) * doublen);

		ct = cnt = tot = 0;

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

			scanf("%s%s", A, B);

			int lena = strlen(A), lenb = strlen(B);

			a = b = 0;

			for (int j = 1; j < lena; ++j) a = a * 10 + A[j] - 48;

			for (int j = 1; j < lenb; ++j) b = b * 10 + B[j] - 48;

			--a; --b;

			if (A[0] == 'h') a += n;

			if (B[0] == 'h') b += n;

			ins((a + n) % doublen, b);

			ins((b + n) % doublen, a);

		}

		for (int i = 0; i < doublen; ++i)

			if (!dfn[i])

				tarjan(i);

		bool flag = false;

		for (int i = 0; i < n; ++i)

			if (bel[i] == bel[i + n]) {

				flag = true;

				puts("BAD");

				break;

			}

		if (!flag) puts("GOOD");

	}

	return 0;

}

巴特西

【hihoCoder 第133周】2-SAT·hihoCoder音乐节

最新文章

热门文章