POJ-3678 : Katu Puzzle

問題概要

bool変数X[i] (|X|<1000)がある。X[a[i]] op[i] X[b[i]] = c[i] (op[i]はand, or, xorのいずれか)が与えられる(|a|<10^6)ので、すべてを満たすような割り当てが存在するか判定する問題。

解法

2SATを解くのと同じように考えれば解ける。例えばa&b=1だと!a->a, !b->bと置き換えれば良い。

acceptされたコード

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

const int MAX_V = 2000;

int V;
vector<int> graph[MAX_V];
vector<int> rev_graph[MAX_V];
int cmp[MAX_V];

namespace StronglyConnectedComponent{
	vector<int> st;
	bool visited[MAX_V];

	void add_edge(int from, int to){
		graph[from].push_back(to);
		rev_graph[to].push_back(from);
	}

	void dfs(int v){
		visited[v] = true;
		for(int i=0; i<(int)graph[v].size(); ++i){
			const int u = graph[v][i];
			if(!visited[u]){
				dfs(u);
			}
		}
		st.push_back(v);
	}

	void rev_dfs(int v, int k){
		visited[v] = true;
		cmp[v] = k;
		for(int i=0; i<(int)rev_graph[v].size(); ++i){
			const int u = rev_graph[v][i];
			if(!visited[u]){
				rev_dfs(u, k);
			}
		}
	}

	int scc(){
		memset(visited, false, sizeof(visited));
		st.clear();
		for(int v=0; v<V; ++v){
			if(!visited[v]){
				dfs(v);
			}
		}
		memset(visited, false, sizeof(visited));
		int k = 0;
		for(;!st.empty();){
			const int v = st.back();
			st.pop_back();
			if(!visited[v]){
				rev_dfs(v, k++);
			}
		}
		return k;
	}
}

using StronglyConnectedComponent::add_edge;
using StronglyConnectedComponent::scc;

void init() {
	int M;
	scanf("%d%d", &V, &M);
	V *= 2;

	//2*i for x_i, 2*i+1 for !x_i
	for (int _ = 0; _ < M; ++_) {
		int a, b, c;
		char buf[10];
		scanf("%d%d%d %s", &a,&b,&c,buf);
		if (buf[0] == 'A') {
			if (c == 1) {
				add_edge(2*a+1, 2*a+0);
				add_edge(2*b+1, 2*b+0);
			}
			else {
				add_edge(2*a+0, 2*b+1);
				add_edge(2*b+0, 2*a+1);
			}
		}
		else if (buf[0] == 'O') {
			if (c == 1) {
				add_edge(2*a+1, 2*b+0);
				add_edge(2*b+1, 2*a+0);
			}
			else {
				add_edge(2*a+0, 2*a+1);
				add_edge(2*b+0, 2*b+1);
			}
		}
		else if (buf[0] == 'X') {
			if (c == 1) {
				add_edge(2*a+1, 2*b+0);
				add_edge(2*a+0, 2*b+1);
				add_edge(2*b+1, 2*a+0);
				add_edge(2*b+0, 2*a+1);
			}
			else {
				add_edge(2*a+1, 2*b+1);
				add_edge(2*a+0, 2*b+0);
				add_edge(2*b+1, 2*a+1);
				add_edge(2*b+0, 2*a+0);
			}
		}
	}
}

bool solve() {
	scc();
	for (int i = 0; i < V/2; ++i) {
		if (cmp[2*i] == cmp[2*i+1]) {
			return false;
		}
	}
	return true;
}

int main() {
	init();
	puts(solve() ? "YES" : "NO");

	return 0;
}