一个奶牛有两个选择方案，要么A成立B不成立，要么A不成立则B成立。所以可以2——sat建图，然后每个方案检查一下就行。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 #define LL long long 9 #define clc(a,b) memset(a,b,sizeof(a))10 const int maxn = 2000 + 10;11 int r(){12 int x=0;char ch=getchar();13 while(ch<'0'||ch>'9')ch=getchar();14 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}15 return x;16 }17 18 int n,m,cnt;19 int head[2010],ans[2010];20 bool used[2010];21 char ch[3]={ '?','N','Y'};22 struct edge{23 int v,next;24 }e[8010];25 26 int get(){27 int x=r();char c=getchar();28 while(c!='Y'&&c!='N')29 c=getchar();30 if(c=='Y') x=x*2-1;31 else x=x*2;32 return x;33 }34 35 void add(int u,int v){36 e[cnt].v=v;37 e[cnt].next=head[u];38 head[u]=cnt++;39 }40 41 void dfs(int x){42 used[x]=true;43 for(int i=head[x];i!=-1;i=e[i].next){44 int v=e[i].v;45 if(!used[v])46 dfs(v);47 }48 }49 bool check(int x){50 clc(used,0);51 dfs(x);52 for(int i=1;i<=n;i++){53 if(used[i*2]&&used[i*2-1])54 return false; 55 } 56 return true;57 }58 int main(){59 n=r(),m=r();60 cnt=0;61 clc(head,-1);62 for(int i=1;i<=m;i++){63 int a,b,c,d;64 a=get();c=get();65 if(a&1) b=a+1;66 else b=a-1;67 if(c&1) d=c+1;68 else d=c-1;69 add(d,a),add(b,c);70 }71 for(int i=1;i<=n;i++){ //如果N，Y结果刚好相反交换一下p,q72 bool p=check(i*2-1);73 bool q=check(i*2);74 //printf("p:%d q:%d\n",p,q);75 if(!q&&!p){76 printf("IMPOSSIBLE\n");77 return 0;78 }79 else if(!p)80 ans[i]=1;81 else if(q&&p)82 ans[i]=0;83 else 84 ans[i]=2;85 }86 for(int i=1;i<=n;i++){87 printf("%c",ch[ans[i]]);88 }89 printf("\n");90 return 0;91 }