POJ 3678 Katu Puzzle(2 - SAT) - from lanshui_Yang
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.
Input
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
Output a line containing "YES" or "NO".
Sample Input
4 4
0 1 1 AND
1 2 1 OR
3 2 0 AND
3 0 0 XOR
Sample Output
YES
Hint
X0 = 1, X1 = 1, X2 = 0, X3 = 1.
제목: n 개의 변수 와 m 개의 조건 이 있 습 니 다. 각 조건 의 형식 은 다음 과 같 습 니 다.
a, b, c, 연산 문자열 op (AND, OR, XOR 등) 세 개 를 드 리 겠 습 니 다. Xa op Xb = c 를 요구 합 니 다.
― 모든 변수 에 값 (0 또는 1) 을 부여 하여 모든 조건 을 만족 시 킬 수 있 습 니까?
문제 풀이 방향: 이 문 제 는 2 - SAT 문제 의 변형 이다. 2 - SAT 문제 에서 조건 을 통 해 그림 의 변 을 만 드 는 것 이다. 이 문제 도 비슷 하고 조건 을 통 해 해당 하 는 변 을 만들어 야 한다. 다만 세부 적 인 부분 은 주의해 야 한다.
코드 를 보십시오:
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<cstdio>
#include<queue>
#define mem(a , b) memset(a , b , sizeof(a))
using namespace std ;
const int MAXN = 10000 ;
vector<int> G[MAXN * 2] ;
bool mark[MAXN * 2] ;
int S[MAXN] , c ; //
char op[8] ;
int n , m ;
int pan ; //
void chu()
{
int i ;
for(i = 0 ; i < n * 2 ; i ++)
G[i].clear() ;
mem(mark , 0) ;
}
void init()
{
chu() ;
pan = 0 ;
int i ;
for(i = 0 ; i < m ; i ++)
{
int a , b , c ;
scanf("%d%d%d" , &a , &b , &c) ;
scanf("%s" , op) ;
if(op[0] == 'A')
{
if(c == 1) //
{
G[2 * a].push_back(2 * a + 1) ;
G[2 * b].push_back(2 * b + 1) ;
}
else
{
G[2 * a + 1].push_back(2 * b) ;
G[2 * b + 1].push_back(2 * a) ;
}
}
else if(op[0] == 'X')
{
if(c == 0)
{
G[2 * a].push_back(2 * b) ;
G[2 * a + 1].push_back(2 * b + 1) ;
G[2 * b].push_back(2 * a) ;
G[2 * b + 1].push_back(2 * a + 1) ;
}
else
{
G[2 * a].push_back(2 * b + 1) ;
G[2 * a + 1].push_back(2 * b) ;
G[2 * b].push_back(2 * a + 1) ;
G[2 * b + 1].push_back(2 * a) ;
}
}
else
{
if(c == 0) //
{
G[2 * a + 1].push_back(2 * a) ;
G[2 * b + 1].push_back(2 * b) ;
}
else
{
G[2 * a].push_back(2 * b + 1) ;
G[2 * b].push_back(2 * a + 1) ;
}
}
}
}
bool dfs(int x)
{
if(mark[x ^ 1]) return false ;
if(mark[x]) return true ;
mark[x] = true ;
S[c ++] = x ;
int i ;
for(i = 0 ; i < G[x].size() ; i ++)
{
if(!dfs(G[x][i]))
return false ;
}
return true ;
}
void solve()
{
if(pan)
puts("NO") ;
else
{
int i ;
for(i = 0 ; i < n ; i ++)
{
if(!mark[i * 2] && !mark[i * 2 + 1])
{
c = 0 ;
if(!dfs(i * 2))
{
while (c > 0)
{
mark[ S[-- c] ] = false ;
}
if(!dfs(i * 2 + 1))
{
pan = 1 ;
break ;
}
}
}
}
if(pan)
puts("NO") ;
else
puts("YES") ;
}
}
int main()
{
while (scanf("%d%d" , &n , &m) != EOF)
{
init() ;
solve() ;
}
return 0 ;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
UVa 110 순환 정렬 프로그램 없음제목: Pascal의 정렬 프로그램을 구성합니다.처음에 보면 Pascal 프로그램을 썼는데 모르는 것은 어려울 줄 알았지만 사실은 프로그램의 대부분이 고정되어 있고 직접printf를 쓰면 된다. 주로 비교적인if-e...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.