BZOJ 1823 [JSOI2010]满汉全席

题目大意

给你N个原材料(标号1~n)，每个原材料有两种制作方法0/1，还有M个评委，每个评委认为如果第$X_i$个原材料不是用方式$A_i$而且第$Y_i$个原材料不是用方式$B_i$制作的那么就不行。问是否存在一种可行制作方案。

2-SAT第一题

最开始我用求方案的2-SAT（DFS）过的，时间复杂度$O(n^2)$

后来觉得不太好，那就学习一下正宗的2-SAT吧qwq

2-SAT，中文译为2-判定性问题，是一种非常特殊的关系型可行解问题。

题目的大概特征就是N个物体，每个物体有两种状态，之后有一些关系，每个关系形如“如果$X_i$号物品选择$A_i$那么$Y_i号物品必须选择$B_i$$”。

这个东西的解决办法如下：

首先对于每一个物品，拆成两种状态（两个点）。

之后进行连边。$A \to B$表示选A就一定选B。

之后跑Tarjan缩点。缩点之后图中的环就会被缩成一个点。环中所有的点要么都不选要么都选，所以里面如果有同一种物品的两种状态，那就无解了。

如果同一物品的两种状态不在同一个强连通分量中那么肯定就可以了。

之后如果可以而且需要求方案的话就需要对新图进行拓扑排序。这里只是求可行性所以就不用拓扑排序了。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
 
#define N 1000
#define M 10000
 
int T,n,m,ix,iy,np,low[N],dep[N],bel[N],st[N],top,cnt;
int to[M],nex[M],head[N],tot;
bool ins[N],BAD;
 
inline void AE(int tx,int ty)
{
    to[++tot]=ty,nex[tot]=head[tx],head[tx]=tot;
}
 
inline int RI()
{
    int ret=0,ano=0;
    char tmp=getchar();
    while(tmp<'0'||tmp>'9')
    {
        if(tmp=='m') ano=1;
        tmp=getchar();
    }
    while(tmp>='0'&&tmp<='9')
    {
        ret=ret*10+tmp-'0';
        tmp=getchar();
    }
    return ((ret-1)<<1)|ano;
}
 
void tarjan(int pos)
{
    ins[pos]=true,st[++top]=pos,low[pos]=dep[pos]=++cnt;
    for(int i=head[pos];i;i=nex[i])
    {
        if(!dep[to[i]])
        {
            tarjan(to[i]);
            low[pos]=min(low[pos],low[to[i]]);
        }
        else if(ins[to[i]])
            low[pos]=min(low[pos],dep[to[i]]);
    }
    if(low[pos]==dep[pos])
    {
        ++np;
        do
        {
            ins[st[top]]=false;
            bel[st[top]]=np;
        }while(st[top--]!=pos);
    }
}
 
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        memset(head,0,sizeof head);
        memset(dep,0,sizeof dep);
        tot=cnt=np=BAD=0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;++i)
        {
            ix=RI(),iy=RI();
            AE(ix^1,iy),AE(iy^1,ix);
        }
        for(int i=1;i<=(n<<1);++i)
            if(!dep[i])
                tarjan(i);
        for(int i=0;i<=n;++i)
            if(bel[i<<1]==bel[(i<<1)|1])
            {
                printf("BAD\n");
                BAD=true;
                break;
            }
        if(!BAD) printf("GOOD\n");
    }
}

DFS版本时间复杂度$O(N^2)$

#include <cstdio>
#include <cstring>
int k,n,m,s[10010],tops,inx,iny;
int to[10010],nex[10010],head[210],tot;
bool mark[210];
int input()
{
    int res=0;
    bool flg=false;
    char tmp=getchar();
    while(tmp!='m'&&tmp!='h') tmp=getchar();
    flg=tmp=='m';
    tmp=getchar();
    while(tmp>='0'&&tmp<='9')
    {
        res=(res<<3)+(res<<1)+tmp-'0';
        tmp=getchar();
    }
    res+=flg?res:res-1;
    return res-1;
}
void addedge(int tx,int ty)
{
    to[++tot]=ty,nex[tot]=head[tx];head[tx]=tot;
}
bool dfs(int pos)
{
    if(mark[pos^1]) return false;
    if(mark[pos]) return true;
    mark[pos]=true;
    s[++tops]=pos;
    for(int i=head[pos];i;i=nex[i])
        if(!dfs(to[i])) return false;
    return true;
}
bool solve()
{
    for(int i=0;i<(n<<1);++i)
        if(mark[i]==false&&mark[i^1]==false)
        {
            tops=0;
            if(!dfs(i))
            {
                while(tops) mark[s[tops--]]=false;
                if(!dfs(i^1)) return false;
            }
        }
    return true;
}
int main()
{
    scanf("%d",&k);
    while(k--)
    {
        memset(head,0,sizeof head);
        memset(mark,false,sizeof mark);
        tot=0;
        scanf("%d%d",&n,&m);
        while(m--)
        {
            inx=input(),iny=input();
            addedge(iny^1,inx);
            addedge(inx^1,iny);
        }
        printf("%s\n",solve()?"GOOD":"BAD");
    }
}