LGP4171 [JSTS 2010] 满汉全席 学习笔记
Luogu Link
前言
鸡 猪 鱼 牛
肉 肉 肉 肉
（这里本来应有一段创主关于汉、满、苗各民族文蛮属性的魔怔言论，但是我记不清了，所以略去。）
题意简述
在原版板子的基础上，那些布尔变量变成了一个取值有两种的变量。好吧其实和布尔变量是等价的。
做法解析
我觉得没什么好解析的。纯纯换皮板子。
所以你也可以认为这篇题解纯属凑数的。大概吧。
代码实现
但是这个换皮板子是带多测的。
#include <bits/stdc++.h>
using namespace std;
using namespace obasic;
const int MaxN=1e2+5;
int N,M,X,Y,ya,yb,na,nb;char ch[2];
int dfn[MaxN<<1],low[MaxN<<1],stk[MaxN<<1],ktp;
vector<int> Gr[MaxN<<1];
int tot,ccnt,bel[MaxN<<1];
void befinit(int n){int nn=n<<1;fill(dfn,dfn+nn+1,0),fill(low,low+nn+1,0);fill(bel,bel+nn+1,0),tot=ccnt=0;for(int i=1;i<=nn;i++)Gr[i].clear();
}
void tarjan(int u){dfn[u]=low[u]=++tot,stk[++ktp]=u;for(auto v : Gr[u]){if(!dfn[v])tarjan(v),minner(low[u],low[v]);else if(!bel[v])minner(low[u],dfn[v]);}if(dfn[u]==low[u]){ccnt++;int v;for(int v;ktp;){v=stk[ktp--],bel[v]=ccnt;if(v==u)break;}}
}
bool twosat(int n){for(int i=1;i<=2*n;i++)if(!dfn[i])tarjan(i);for(int i=1;i<=n;i++)if(bel[i]==bel[i+n])return false;return true;
}
void mian(){readis(N,M);befinit(N);for(int i=1;i<=M;i++){scanf(" %c%d %c%d",&ch[0],&X,&ch[1],&Y);ya=(ch[0]=='h'),yb=(ch[1]=='h');na=ya^1,nb=yb^1;Gr[X+na*N].push_back(Y+yb*N);Gr[Y+nb*N].push_back(X+ya*N);}puts(twosat(N)?"GOOD":"BAD");
}
int Tcn;
int main(){readi(Tcn);while(Tcn--)mian();return 0;
}