题目大意

有$n$种材料，$m$个评委，每种材料有两种不同的做法只能选择一种

然而每个评委有两个要求，做出来的菜必须满足每一个评委至少一个要求

问是否有这样的方案

数据范围

$n\leqslant 100,m\leqslant 1000$

题解

每种菜两种做法只能选择一种，就是明显的$2-SAT$

每个评委有两个要求至少要满足一个，根据这个关系来构图

构图之后，强连通分量缩点，然后就开始找是否有一种菜的两种做法都在同一个强连通子图中

没有就说明总有一种方案满足题目条件，反之就一定没有

程序

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define goedge(i,x) for(int i=last[x];i;i=e[i].next)
using namespace std;

struct edge{int to,next;}e[2050];
int last[1050],q[1050],flag[1050];
int dfn[1050],low[1050],belong[1050];
int t,n,m,et,top,dfn_tot,scc_tot;
inline void addedge(int u,int v){e[++et].to=v;e[et].next=last[u];last[u]=et;}
inline int check(){
    For(i,1,n) if (belong[2*i]==belong[2*i^1]) return 0;
    return 1;
}

void tarjan(int x){
    low[x]=dfn[x]=++dfn_tot;
    flag[x]=1;q[++top]=x;
    goedge(i,x)
        if (!dfn[e[i].to]){tarjan(e[i].to);low[x]=min(low[x],low[e[i].to]);}
        else if (flag[e[i].to]) low[x]=min(low[x],dfn[e[i].to]);
    if (low[x]==dfn[x]){
        scc_tot++;
        int now=0;
        while(now!=x){
            now=q[top--];
            belong[now]=scc_tot;
            flag[now]=0;
        }
    }
}

int main(){
    scanf("%d",&t);
    while(t--){
        et=top=dfn_tot=scc_tot=0;
        memset(last,0,sizeof(last));memset(flag,0,sizeof(flag));
        memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));
        scanf("%d%d",&n,&m);
        For(i,1,m){
            int x,y;char c1,c2;
            getchar();scanf("%c%d %c%d",&c1,&x,&c2,&y);
            x=(x<<1)+(c1=='h');
            y=(y<<1)+(c2=='h');
            addedge(x^1,y);addedge(y^1,x);
        }
        For(i,2,2*n+1) if (!dfn[i]) tarjan(i);
        if (check()) puts("GOOD");
        else puts("BAD");
    }
    return 0;
}