P4171 [JSOI2010]满汉全席（2-SAT）

2-SAT裸题

把每一道菜拆成两个点分别表示用汉式或满式

连边可以参考板子->这里

然后最尴尬的是我没发现$n<=100$然后化成整数的时候只考虑了$s[1]$结果炸掉了2333

 1 //minamoto
 2 #include<cstdio>
 3 #include<cstring>
 4 template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
 5 const int N=205,M=2005;
 6 int head[N],Next[M],ver[M],tot;
 7 inline void add(int u,int v){
 8     ver[++tot]=v,Next[tot]=head[u],head[u]=tot;
 9 }
10 int dfn[N],low[N],bl[N],st[N],num,cnt,top,n,m;
11 inline void clear(){
12     memset(dfn,0,sizeof(dfn)),
13     memset(low,0,sizeof(low)),
14     memset(bl,0,sizeof(bl)),
15     memset(st,0,sizeof(st)),
16     memset(head,0,sizeof(head));
17     top=cnt=num=tot=0;
18 }
19 void tarjan(int u){
20     dfn[u]=low[u]=++num,st[++top]=u;
21     for(int i=head[u];i;i=Next[i]){
22         int v=ver[i];
23         if(!dfn[v]) tarjan(v),cmin(low[u],low[v]);
24         else if(!bl[v]) cmin(low[u],dfn[v]);
25     }
26     if(dfn[u]==low[u]) for(++cnt;st[top+1]!=u;--top) bl[st[top]]=cnt;
27 }
28 char s[5],ss[5];
29 void solve(){
30     clear();
31     scanf("%d%d",&n,&m);
32     for(int i=1;i<=m;++i){
33         scanf("%s%s",s,ss);
34         int a=s[0]=='m',c=ss[0]=='m';
35         int b=0,d=0,k;
36         k=1;while(s[k]>='0'&&s[k]<='9') b=b*10+s[k++]-'0';
37         k=1;while(ss[k]>='0'&&ss[k]<='9') d=d*10+ss[k++]-'0';
38         add(b+(!a)*n,d+c*n),add(d+(!c)*n,b+a*n);
39     }
40     for(int i=1,l=2*n;i<=l;++i) if(!dfn[i]) tarjan(i);
41     for(int i=1;i<=n;++i)
42     if(bl[i]==bl[i+n]) return (void)(puts("BAD"));
43     puts("GOOD");
44 }
45 int main(){
46 //    freopen("testdata.in","r",stdin);
47     int T;scanf("%d",&T);
48     while(T--) solve();
49     return 0;
50 }