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; }