BZOJ1823：[JSOI2010]满汉全席—

BZOJ1823：[JSOI2010]满汉全席——题解

阅读量：5952 次

发布时间：2019-06-19

本文共 1569 字，大约阅读时间需要 5 分钟。

题面太长啦就不粘过来啦！

裸的2-SAT用来练板子的。

显然属于“a和b之间必须选一种”模型，只要a'向b连边，b'向a连边即可。

（被这题读入坑了orz）

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;typedef long long ll;const int N=1005;const int M=20005;struct node{ int to,nxt;}e[M];int T,n,m,head[N],cnt;int dfn[N],low[N],t,l;int to[N];bool inq[N];stack
             
              q;inline int neg(int x){ if(x>n)return x-n; return x+n;}inline void add(int u,int v){ e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;}void tarjan(int u){ dfn[u]=low[u]=++t; q.push(u);inq[u]=1; for(int i=head[u];i;i=e[i].nxt){ int v=e[i].to; if(!dfn[v]){ tarjan(v); low[u]=min(low[u],low[v]); }else if(inq[v]){ low[u]=min(low[u],dfn[v]); } } if(dfn[u]==low[u]){ int v;l++; do{ v=q.top();q.pop(); inq[v]=0;to[v]=l; }while(u!=v); }}inline void init(){ cnt=t=l=0; memset(head,0,sizeof(head)); memset(dfn,0,sizeof(dfn));}inline int get(){ int k;char ch=0; while(ch!='m'&&ch!='h')ch=getchar(); scanf("%d",&k); if(ch=='h')k+=n; return k;}int main(){ scanf("%d",&T); while(T--){ init(); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ int a=get(),b=get(); add(neg(a),b); add(neg(b),a); } for(int i=1;i<=2*n;i++) if(!dfn[i])tarjan(i); bool flag=1; for(int i=1;i<=n&&flag;i++){ if(to[i]==to[i+n])flag=0; } if(flag)puts("GOOD"); else puts("BAD"); }}