bzoj1823 [JSOI2010]满汉全席

题目

2-sat裸题，最近刚刚学了这个东西，毕竟NOI考过呀。

建边就是考虑限制条件如果x选什么，y就一定选什么之类的，然后跑一遍tarjan缩点，如果存在一个点和它的相反点在一个强连通分量中，那么就没解，否则一定有解。

至于输出一个解，只要看mark的大小就好了，选小的就好了。

#include<bits/stdc++.h>
#define N 100000
using namespace std;
int T,n,m,ans; 
int first[N+5],to[N+5],nxt[N+5],siz; 
char op1[N+5],op2[N+5];
int id1[N+5],id2[N+5];
int dfn[N+5],low[N+5],ind,mark[N+5],id;
int stk[N+5],in[N+5],top;
inline void link(int x,int y)
{
    nxt[siz]=first[x];
    first[x]=siz;
    to[siz++]=y;
}
inline char nc()
{
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    int x=0,b=1;
    char c=nc();
    for(;!(c<='9'&&c>='0');c=nc())if(c=='-')b=-1;
    for(;c<='9'&&c>='0';c=nc())x=x*10+c-'0';
    return x*b;
}
inline void write(int x)
{
    if(x==0)putchar('0');
    else
    {
        char buf[15];
        int len=0;
        if(x<0)putchar('-'),x=-x;
        while(x)buf[++len]=x%10+'0',x/=10;
        for(int i=len;i>=1;i--)putchar(buf[i]);
    }
    putchar(' ');
}
inline void tarjan(int x)
{
    dfn[x]=low[x]=++ind;
    stk[++top]=x,in[x]=true;
    for(int i=first[x];i!=-1;i=nxt[i])
    {
        int u=to[i];
        if(!dfn[u])tarjan(u),low[x]=min(low[x],low[u]);
        else if(in[u])low[x]=min(low[x],dfn[u]);
    }
    if(dfn[x]==low[x])
    {
        id++;int tmp;
        do
        {
            tmp=stk[top--];
            mark[tmp]=id;
            in[tmp]=false;
        }while(tmp!=x);
    }
}
int main()
{
    freopen("in.txt","r",stdin);
    scanf("%d\n",&T);
    while(T--)
    {
        memset(first,-1,sizeof(first)),siz=0;
        scanf("%d %d\n",&n,&m);
        for(int i=1;i<=m;i++)scanf("%c%d %c%d\n",&op1[i],&id1[i],&op2[i],&id2[i]);
        for(int i=1;i<=m;i++)
        {
            if(op1[i]=='m'&&op2[i]=='h')link(id1[i]+n,id2[i]+n),link(id2[i],id1[i]);
            if(op1[i]=='h'&&op2[i]=='m')link(id1[i],id2[i]),link(id2[i]+n,id1[i]+n);
            if(op1[i]=='m'&&op2[i]=='m')link(id1[i]+n,id2[i]),link(id2[i]+n,id1[i]);
            if(op1[i]=='h'&&op2[i]=='h')link(id1[i],id2[i]+n),link(id2[i],id1[i]+n);
        }
        memset(mark,0,sizeof(mark));
        memset(dfn,0,sizeof(dfn));
        memset(low,0,sizeof(low));
        id=ind=0;
        for(int i=1;i<=2*n;i++)if(!dfn[i])tarjan(i);
        ans=1;
        for(int i=1;i<=n;i++)if(mark[i]==mark[i+n])ans=0;
        if(ans)printf("GOOD\n");
        else printf("BAD\n");
    } 
    return 0;
}