POJ3678 Katu Puzzle 【2-sat】

题目

Katu Puzzle is presented as a directed graph G(V, E) with each edge e(a, b) labeled by a boolean operator op (one of AND, OR, XOR) and an integer c (0 ≤ c ≤ 1). One Katu is solvable if one can find each vertex Vi a value Xi (0 ≤ Xi ≤ 1) such that for each edge e(a, b) labeled by op and c, the following formula holds:

Xa op Xb = c

The calculating rules are:

AND 0 1

0 0 0

1 0 1

OR 0 1

0 0 1

1 1 1

XOR 0 1

0 0 1

1 1 0

Given a Katu Puzzle, your task is to determine whether it is solvable.

输入格式

The first line contains two integers N (1 ≤ N ≤ 1000) and M,(0 ≤ M ≤ 1,000,000) indicating the number of vertices and edges.

The following M lines contain three integers a (0 ≤ a < N), b(0 ≤ b < N), c and an operator op each, describing the edges.

输出格式

Output a line containing "YES" or "NO".

输入样例

4 4

0 1 1 AND

1 2 1 OR

3 2 0 AND

3 0 0 XOR

输出样例

YES

提示

X0 = 1, X1 = 1, X2 = 0, X3 = 1.

题解

跪了。。。就因为n << 1写成了1 << n QAQ

这题加深了我对2-sat建图的理解，建边就表示选择了起点就必须选择终点

对于每个限制条件，我们分别考虑选择x的不同值

AND

为1，则x0->x1，y0->y1，让x0，y0自相矛盾，无法选择

为0，则x0->y1，y0->x1

OR

为1，则x0->y1，y0->x1

为0，则x1->x0，y1->y0

XOR

为1，则x0->y1，x1->y0，y1->x0，y0->x1

为0，则x0->y0，x1->y1，y0->x0，y1->x1

tarjan判断一下x0和x1是否在同一个强联通分量即可

#include<iostream>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long int

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)

#define cls(x) memset(x,0,sizeof(x))

using namespace std;

const int maxn = 4005,maxm = 4000005,INF = 1000000000;

int n,m,h[maxn],ne;

struct EDGE{int to,nxt;}ed[maxm];

void build(int u,int v){ed[ne] = (EDGE){v,h[u]}; h[u] = ne++;}

int dfn[maxn],low[maxn],Scc[maxn],st[maxn],scci,top,cnt;

void dfs(int u){

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

	st[++top] = u;

	Redge(u){

		if (!dfn[to = ed[k].to]){

			dfs(to);

			low[u] = min(low[u],low[to]);

		}else if (!Scc[to]) low[u] = min(low[u],dfn[to]);

	}

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

		scci++;

		do{Scc[st[top]] = scci;}while (st[top--] != u);

	}

}

char opt[10];

int main(){

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

		int a,b,v,x0,x1,y0,y1; cnt = scci = top = 0; ne = 1;

		cls(dfn); cls(h); cls(Scc); cls(low);

		while (m--){

			scanf("%d%d%d%s",&a,&b,&v,opt);

			x0 = a << 1; x1 = x0 | 1; y0 = b << 1; y1 = y0 | 1;

			if (opt[0] == 'A'){

				if (v) build(x0,x1),build(y0,y1);

				else build(x1,y0),build(y1,x0);

			}

			else if (opt[0] == 'O'){

				if (v) build(x0,y1),build(y0,x1);

				else build(x1,x0),build(y1,y0);

			}

			else if (opt[0] == 'X'){

				if (v) build(x0,y1),build(y0,x1),build(x1,y0),build(y1,x0);

				else build(x1,y1),build(y0,x0),build(x0,y0),build(y1,x1);

			}

		}

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

		bool flag = true;

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

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

				flag = false; break;

			}

		if (flag) printf("YES\n");

		else printf("NO\n");

	}

	return 0;

}

巴特西

POJ3678 Katu Puzzle 【2-sat】

题目

输入格式

输出格式

输入样例

输出样例

提示

题解

最新文章

热门文章