Description:

给定一个大小为 的集合 ,其中每个元素的值为 ,现在给出他们之间 对元素逻辑运算的结果 ,问是否存在一种满足所有条件的取值方案,存在输出 ,否则输出

Solution:

一道很基础的 题目。

考虑 的逻辑运算。我们用 表示 表示 ,用 表示 连一条有向边。

根据上述关系建完图之后跑一遍 ,如果存在一个 使得 属于同一个强联通分量那么就无解,否则有解。

Code:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>

using namespace std;

struct bian_
{
    int next;
    int to;
}bian[4000010]={{0,0}};
int First[2010]={0};
int N,M;
int bianp=0;
int stack[2010]={0};
int inst[2010]={0};
int stp=0;
int dfsp=0;
int dfn[2010]={0};
int Low[2010]={0};
int belong[2010]={0};
int bep=0;

void Add(int p,int q,int k)
{
    bian[k].to=q;
    bian[k].next=First[p];
    First[p]=k;
    return;
}

void read_int(int &x)
{
    x=0;
    char ch=getchar();
    for(;ch=='\n' || ch=='\r' || ch=='\0' || ch==' ';ch=getchar());
    for(;ch>='0' && ch<='9';ch=getchar())
        x=x*10+ch-'0';
    return;
}

char getCH()
{
    char ch=getchar();
    for(;ch=='\n' || ch=='\r' || ch=='\0' || ch==' ';ch=getchar());
    for(char tt=getchar();tt>='A' && tt<='Z';tt=getchar());
    return ch;
}

void dfs(int cnt)
{
    dfn[cnt]=++dfsp;
    Low[cnt]=dfn[cnt];
    stack[++stp]=cnt;
    inst[cnt]=1;
    for(int i=First[cnt];i!=0;i=bian[i].next)
    {
        int u=bian[i].to;
        if(dfn[u]==0)
        {
            dfs(u);
            Low[cnt]=min(Low[cnt],Low[u]);
        }
        else if(inst[u]==1)
            Low[cnt]=min(Low[cnt],dfn[u]);
    }
    if(Low[cnt]==dfn[cnt])
    {
        bep++;
        for(;;)
        {
            int u=stack[stp];
            stack[stp--]=0;
            belong[u]=bep;
            inst[u]=0;
            if(u==cnt) break;
        }
    }
    return;
}

int main()
{
    cin>>N>>M;
    for(int i=1;i<=M;i++)
    {
        int p,q,r;
        read_int(p);read_int(q);read_int(r);
        p++,q++;
        char str=getCH();
        if(str=='A')
        {
            if(r==1)
            {
                Add(p<<1,(p<<1)-1,++bianp);
                Add(q<<1,(q<<1)-1,++bianp);
            }
            else
            {
                Add((p<<1)-1,q<<1,++bianp);
                Add((q<<1)-1,p<<1,++bianp);
            }
        }
        else if(str=='O')
        {
            if(r==1)
            {
                Add(p<<1,(q<<1)-1,++bianp);
                Add(q<<1,(p<<1)-1,++bianp);
            }
            else
            {
                Add((p<<1)-1,p<<1,++bianp);
                Add((q<<1)-1,q<<1,++bianp);
            }
        }
        else if(str=='X')
        {
            int P[2]={(p<<1)-1,p<<1};
            int Q[2]={(q<<1)-1,q<<1};
            Add(P[0],Q[r],++bianp);
            Add(P[1],Q[r^1],++bianp);
            Add(Q[0],P[r],++bianp);
            Add(Q[1],P[r^1],++bianp);
        }
    }
    for(int i=1;i<=(N<<1);i++)
    {
        if(dfn[i]==0)
            dfs(i);
    }
    for(int i=1;i<=N;i++)
    {
        if(belong[i<<1]==belong[(i<<1)-1])
        {
            puts("NO");
            return 0;
        }
    }
    puts("YES");
    return 0;
}