题解 CF1971H ±1

Solution

2-SAT 板子题。

设点 $u_{i}$ 为 $i=-1$ ， $u_{i+n}$ 为 $i=1$ 。

对于每一列，最少要有两个 $1$ 。这意味着，若一列中的一个数为 $-1$ ，则其余两个数必定为 $1$ ，这就得到了两条有向边。我们分别假设一列中的三个数为 $-1$ ，就得到了 $6$ 条有向边。因为有 $n$ 列，所以一共有 $6n$ 条有向边。然后跑 Tarjan，判断是否有 $u_{i}$ 、 $u_{i+n}$ 在同一强连通分量内即可。

code

#include <bits/stdc++.h>
#define N 100010
using namespace std;
typedef long long ll;

template <typename T> inline void read(T &x)
{
	x = 0; T f = 1; char ch = getchar();
	while (!isdigit(ch)) {if (ch == '-') f = -f; ch = getchar();}
	while (isdigit(ch)) {x = x * 10 + ch - 48; ch = getchar();}
	x *= f;
}

int T, n, head[N], edge_cnt, a[4][N], dfn[N], low[N], col, cnt, co[N], top, st[N];
struct Node {
	int nxt, v;
} e[N << 1];

void add_edge(int u, int v)
{
	e[++edge_cnt].nxt = head[u];
	head[u] = edge_cnt;
	e[edge_cnt].v = v;
}

void tarjan(int u)
{
	dfn[u] = low[u] = ++cnt;
	st[++top] = u;
	for (int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].v;
		if (!dfn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
		} else if (!co[v])
			low[u] = min(low[u], dfn[v]);
	}
	if (low[u] == dfn[u]) {
		co[u] = ++col;
		while (st[top] != u)
			co[st[top--]] = col;
		--top;
	}
}

void WORK()
{
	edge_cnt = cnt = col = top = 0;
	memset(head, 0, sizeof(head));
	memset(dfn, 0, sizeof(dfn));
	memset(low, 0, sizeof(low));
	memset(co, 0, sizeof(co));
	read(n);
	for (int i = 1; i <= 3; i++)
		for (int j = 1; j <= n; j++)
			read(a[i][j]);
	for (int i = 1; i <= n; i++) {
		add_edge((a[1][i] < 0 ? -a[1][i] + n : a[1][i]), (a[2][i] < 0 ? -a[2][i] : a[2][i] + n));
		add_edge((a[1][i] < 0 ? -a[1][i] + n : a[1][i]), (a[3][i] < 0 ? -a[3][i] : a[3][i] + n));
		add_edge((a[2][i] < 0 ? -a[2][i] + n : a[2][i]), (a[1][i] < 0 ? -a[1][i] : a[1][i] + n));
		add_edge((a[2][i] < 0 ? -a[2][i] + n : a[2][i]), (a[3][i] < 0 ? -a[3][i] : a[3][i] + n));
		add_edge((a[3][i] < 0 ? -a[3][i] + n : a[3][i]), (a[1][i] < 0 ? -a[1][i] : a[1][i] + n));
		add_edge((a[3][i] < 0 ? -a[3][i] + n : a[3][i]), (a[2][i] < 0 ? -a[2][i] : a[2][i] + n));
	}
	for (int i = 1; i <= (n << 1); i++)
		if (!dfn[i])
			tarjan(i);
	for (int i = 1; i <= n; i++)
		if (co[i] == co[i + n]) {
			printf("NO\n");
			return;
		}
	printf("YES\n");
}

int main()
{
	read(T);
	while (T--) WORK();
	return 0;
}