题意

题意翻译

简述：给出(n)个法案，(m)头牛的意见，每头牛有两个表决格式为“支持或反对某法案”，每头牛需要至少满足一个表决，不可能成立的话输出IMPOSSIBLE，否则输出方案，(Y)代表能，(N)代表不能。若是有的解中法案可以通过，有些不能则输出“？”。

由于对(Farmer John)的领导感到极其不悦，奶牛们退出了农场，组建了奶牛议会。

议会以“每头牛都可以获得自己想要的”为原则，建立了下面的投票系统：(M)只到场的奶牛((1leq Mleq 4000))会给(N)个议案投票((1leq Nleq 1,000))。每只奶牛会对恰好两个议案(B_i and C_i (1leq B_ileq N;1leq C_ileq N))投出“是”或“否”（输入文件中的('Y')和('N')）。

他们的投票结果分别为(VB_i(VB_iin {'Y', 'N'})and VC_i (VC_iin {'Y', 'N'}))。最后，议案会以如下的方式决定：每只奶牛投出的两票中至少有一票和最终结果相符合。例如(Bessie)给议案(1)投了赞成('Y')，给议案(2)投了反对('N')，那么在任何合法的议案通过方案中，必须满足议案(1)必须是('Y')或者议案(2)必须是('N')（或者同时满足）。

给出每只奶牛的投票，你的工作是确定哪些议案可以通过，哪些不能。

如果不存在这样一个方案，输出IMPOSSIBLE。

如果至少有一个解，输出：(Y)如果在每个解中，这个议案都必须通过；(N)如果在每个解中，这个议案都必须驳回；"?"如果有的解这个议案可以通过，有的解中这个议案会被驳回。

输入输出格式

输入格式：

Line (1): Two space-separated integers: (N) and (M)
Lines (2dots M+1): Line (i+1) describes cow (i)'s votes with four

space-separated fields -- an integer, a vote, another integer, and another vote: (B_i,VB_i,C_i,VC_i)

输出格式：

Line 1: A string with N characters, where the ith character is either a ('Y') if the (i)th bill must pass, an ('N') if the (i)th bill must fail, or a '?' if it cannot be determined whether the bill passes from these votes.

If there is no solution which satisfies every cow, then output the single line IMPOSSIBLE.

输入输出样例

输入样例#1：

3 4
1 Y 2 N
1 N 2 N
1 Y 3 Y
1 Y 2 Y

输出样例#1：

YN?

思路

关于(2-SAT)问题的学习请参照博客：Luogu P4782 【模板】2-SAT 问题(2-SAT)。

(2-SAT)问题，难点在于要给出准确判定。在这里给出一个(O(n^2))的做法：判断能否从(a)到达(a+n)，以及能否从(a+n)到达(a)。如果能从(a)到达(a+n)，则选择(a+n)；如果能从(a+n)到达(a)，则选择(a)；否则，输出"?"。

判断能否到达，缩点之后(dfs)就好了。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2005,MAXM=10005;
int n,m,tot,js,dfn[MAXN],low[MAXN],bel[MAXN];
int cnt,top[MAXN],to[MAXM],nex[MAXM];
int _cnt,_top[MAXN],_to[MAXM],_nex[MAXM];
bool vis[MAXN];
stack<int>S;
int read()
{
    int re=0;char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) re=(re<<3)+(re<<1)+ch-'0',ch=getchar();
    return re;
}
char readc()
{
    char ch=getchar();
    while(!isalpha(ch)) ch=getchar();
    return ch;
}
void add_edge(int x,int y){to[++cnt]=y,nex[cnt]=top[x],top[x]=cnt;}
void _add_edge(int x,int y){_to[++_cnt]=y,_nex[_cnt]=_top[x],_top[x]=_cnt;}
void tarjan(int now)
{
    dfn[now]=low[now]=++tot,vis[now]=true,S.push(now);
    for(int i=top[now];i;i=nex[i])
        if(!dfn[to[i]]) tarjan(to[i]),low[now]=min(low[now],low[to[i]]);
        else if(vis[to[i]]) low[now]=min(low[now],dfn[to[i]]);
    if(dfn[now]==low[now])
    {
        bel[now]=++js,vis[now]=false;
        while(S.top()!=now) bel[S.top()]=js,vis[S.top()]=false,S.pop();
        S.pop();
    }
}
bool dfs(int now,int des)
{
    if(now==des) return true;
    vis[now]=true;
    for(int i=_top[now];i;i=_nex[i])
        if(!vis[_to[i]]&&dfs(_to[i],des)) return true;
    return false;
}
int main()
{
    n=read(),m=read();
    while(m--)
    {
        int x=read();char xx=readc();
        int y=read();char yy=readc();
        if(xx=='Y'&&yy=='Y') add_edge(x+n,y),add_edge(y+n,x);
        else if(xx=='Y'&&yy=='N') add_edge(x+n,y+n),add_edge(y,x);
        else if(xx=='N'&&yy=='Y') add_edge(x,y),add_edge(y+n,x+n);
        else if(xx=='N'&&yy=='N') add_edge(x,y+n),add_edge(y,x+n);
    }
    for(int i=1;i<=(n<<1);i++) if(!dfn[i]) tarjan(i);
    for(int i=1;i<=n;i++)
        if(bel[i]==bel[i+n])
        {
            printf("IMPOSSIBLE");
            return 0;
        }
    for(int i=1;i<=(n<<1);i++)
        for(int j=top[i];j;j=nex[j])
            if(bel[i]!=bel[to[j]]) _add_edge(bel[i],bel[to[j]]);
    for(int i=1;i<=n;i++)
    {
        memset(vis,false,sizeof vis);
        if(bel[i]<bel[i+n])
        {
            if(dfs(bel[i+n],bel[i])) putchar('Y');
            else putchar('?');
        }
        else if(bel[i]>bel[i+n])
        {
            if(dfs(bel[i],bel[i+n])) putchar('N');
            else putchar('?');
        }
    }
    return 0;
}