[洛谷P4782]【模板】2-SAT 问题

题目大意：有$n$个布尔变量 $x_1 \sim x_n$，另有$m$个需要满足的条件，每个条件的形式都是"$x_i$ 为$true/false$或$x_j$为$true/false$"。比如"$x_1$为$true$或$x_3$为$false$"、"$x_7$为$false$或$x_2$为$false$"。$2-SAT$问题的目标是给每个变量赋值使得所有条件得到满足。

题解：$2-SAT$，若$a$推出$b$，就连两条边，分别为$a -> b$和$!b -> !a$，若$a$一定为$true$，就连一条$!a -> a$（$false$相同），然后$tarjan$缩点，若一个点的两个状态在同一个强连通分量中，就有矛盾，否则那一个状态先访问到就为什么状态

卡点：1.$tarjan$缩点弹出栈时条件写错

C++ Code：

#include <cstdio>

#define maxn 1000010 << 1

using namespace std;

int n, m;

int head[maxn], cnt;

struct Edge {

	int to, nxt;

} e[maxn];

void add(int a, int b) {

	e[++cnt] = (Edge) {b, head[a]}; head[a] = cnt;

}

int low[maxn], DFN[maxn], stack[maxn], res[maxn], tot, idx, CNT;

bool vis[maxn];

inline int min(int a, int b) {return a < b ? a : b;}

void tarjan(int rt) {

	DFN[rt] = low[rt] = ++idx;

	vis[stack[++tot] = rt] = true;

	int v;

	for (int i = head[rt]; i; i = e[i].nxt) {

		v = e[i].to;

		if (DFN[v]) {

			if (vis[v]) low[rt] = min(low[rt], DFN[v]);

		} else {

			tarjan(v);

			low[rt] = min(low[rt], low[v]);

		}

	}

	if (DFN[rt] == low[rt]) {

		CNT++;

		do {

			vis[v = stack[tot--]] = false;

			res[v] = CNT;

		} while (rt != v);

	}

}

int main() {

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

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

		int a, b, c, d;

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

		add(a << 1 | !b, c << 1 | d);

		add(c << 1 | !d, a << 1 | b);

	}

	for (int i = 2; i <= (n << 1 | 1); i++) {

		if (!DFN[i]) tarjan(i);

	}

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

		if (res[i << 1] == res[i << 1 | 1]) {

			puts("IMPOSSIBLE");

			return 0;

		}

	}

	puts("POSSIBLE");

	for (int i = 1; i <= n; i++) printf("%d ", res[i << 1] > res[i << 1 | 1]);

	puts("");

	return 0;

}

巴特西

[洛谷P4782]【模板】2-SAT 问题

最新文章

热门文章