POJ 3678 [실 수 는 항상 자신 에 게 수확 을 가 져 다 준다.]

우선 LRJ 코드 를 확 인 했 습 니 다.
 
   자신 이 한 것 에 대해 자신 이 또 몇 가 지 를 확 정 했 습 니 다. 자신 이 그렇게 먼저 하 라 고 했 습 니 다. 예 를 들 어 3, 6, 1 AND 와 같은 3, 6 이 모두 확 정 된 점 에 대해 자신 이 Num 으로 기록 하면 비참 하 게 죽 었 습 니 다.
 
   나 도 현장 경기 에서 스스로 알고리즘 을 만 들 면 비참 하 게 죽 을 지도 모른다 는 것 을 확신한다.
  
   2 - SAT, 나중에 나 는 갑자기 확 정 된 위치 라 도 이런 대칭 적 인 방법 으로 만 들 수 있다 는 생각 이 들 었 다. 모든 상 태 를 추가 하면 이런 상 태 를 내 놓 을 수 있 지.
 
   그 나 저 나 RANK 에서 상위 권 에 있 는 사람들 은 보통 입 출력 가속 화 를 넣 었 어 요.
 
   그리고 OJ 에 있 는 데 이 터 는 랜 덤 으로 나 올 수도 있어 요.
 
   타 잔 의 2 - SAT 방법 도 배 웠 는데 사실은 사상 이 비슷 하 다.
 
 

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

using namespace std;



//                    。。。。

const int maxn = 1500;

int n,m;

vector<int> G[maxn*3];

bool mark[maxn*3];

int s[maxn*3],c;

char op[10];



bool dfs(int x)

{

    if(mark[x^1]) return false;//            

    if(mark[x]) return true;

    mark[x]=true;

    s[c++]=x;

    for(int i=0;i<G[x].size();i++)

        if(!dfs(G[x][i])) return false;

    return true;

}



void init()

{

    for(int i=0;i<n*2;i++)  G[i].clear();

    memset(mark,0,sizeof(mark));

}



bool solve()

{

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

    {

      if( !mark[i] && !mark[i+1] )

      {

          c = 0;

          if( !dfs(i) )

          {

              while(c>0)

                mark[s[--c]]=false;

              if(!dfs(i+1)) return false;

          }

      }

    }

    return true;

}



int main()

{

    int a,b,c;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        init();

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

        {

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

                if(!strcmp(op,"AND"))

                {

                    if(c==1)

                    {

                        G[a*2].push_back(b*2);//              。   。

                        G[a*2+1].push_back(b*2);



                        G[b*2].push_back(a*2);

                        G[b*2+1].push_back(a*2);

                    }

                    else if(c==0)

                    {

                        G[a*2].push_back(b*2+1);//     

                        G[b*2].push_back(a*2+1);

                    }

                }

                //////////

               else if(!strcmp(op,"OR"))

                {

                    if(c==1)

                    {

                       G[a*2+1].push_back(b*2);//a b    

                       G[b*2+1].push_back(a*2);

                    }

                    else if(c==0)

                    {

                       G[a*2].push_back(b*2+1);

                       G[a*2+1].push_back(b*2+1);//    0



                       G[b*2].push_back(a*2+1);

                       G[b*2+1].push_back(a*2+1);

                    }

                }

               ////////////

              else if(!strcmp("XOR",op))

                {

                    if(c==1)

                    {

                             G[a*2+1].push_back(b*2);

                             G[a*2].push_back(b*2+1);



                             G[b*2+1].push_back(a*2);

                             G[b*2].push_back(a*2+1);

                    }

                    else if(c==0)

                    {

                             G[a*2+1].push_back(b*2+1);

                             G[a*2].push_back(b*2);



                             G[b*2+1].push_back(a*2+1);

                             G[b*2].push_back(a*2);

                    }

               }

        }



        if(solve()==false) printf("NO
");

        else

        {

            printf("YES
");

        }

    }

    return 0;

}