$2-SAT$
前置知识：
题目每回给的条件有 $4$ 个参数，$a,x,b,y$。$x=1$ 代表 $a$ 是真，$x=0$ 代表 $a$ 假，同样 $y$ 也是对 $b$ 的描述。还有一个大条件，就是第一个条件和第二个条件至少有一个符合条件。
我们要对所有的 $a,b$ 赋值，使他们至少一个满足 $x,y$ 的描述。
我们为了建立“稳定”的关系，将他们换一种表达方式：
$a,b$ 至少有一个满足，那么如果强制 $a$ 不满足，那么 $b$ 一定满足。或者强制 $b$ 一定不满足，那么 $a$ 一定满足。
现在我们用这两个条件建图，建出的图会存在强联通分量，而且同一强连通分量内的变量一定相等。
如果发现 $a$ 满足和强制不满足 $a$ 在同一个强联通分量中，那么无解（显然 $1\not =0$）。
可能存在多解情况，但是只要输出一组解即可，在 tarjan 缩点的时候，我们已经将每个强连通分量标好编号，但是是反着的拓扑序。
如果 $x$ 的拓扑序在 $!x$ 之后，取 $x$ 为真即可，但是 tarjan 的顺序是反的，所以 $x$ 的编号在 $!x$ 之前，或者说编号更小，即为真。
代码
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<bitset>
#include<stack>
#include<map>
using namespace std;
long long r_r(){//快读
long long x=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
const int o_o=2e6+10;
int x_x;//当前是第几个被遍历的节点
int c_c;//新点的编号
int d_f[o_o],l_w[o_o];//时间戳
int s_s[o_o],t_p;//存当前环中的编号
int b_b[o_o];//标记入环
int n_w[o_o];//当前节点属于那个新节点
//链式前向星存边
struct po{
int v,n_t;
}p_p[o_o];
int h_d[o_o],x_p;
void a_d(int u,int v){//加边
x_p++;
p_p[x_p].n_t=h_d[u];
p_p[x_p].v=v;
h_d[u]=x_p;
}
void t_j(int k){//tarjan 缩点
d_f[k]=l_w[k]=++x_x;
s_s[++t_p]=k;
b_b[k]=1;
for(int i=h_d[k];i;i=p_p[i].n_t){
int v=p_p[i].v;
if(!d_f[v]){
t_j(v);
l_w[k]=min(l_w[k],l_w[v]);
}else if(b_b[v]) l_w[k]=min(l_w[k],d_f[v]);
}
if(d_f[k]==l_w[k]){//成环
c_c++;
while(s_s[t_p+1]!=k){
n_w[s_s[t_p]]=c_c;//标记新节点
b_b[s_s[t_p]]=0;
t_p--;
}
}
}
int main(){
int n=r_r(),m=r_r();
for(int i=1;i<=m;i++){
int a=r_r(),x=r_r(),b=r_r(),y=r_r();//读入条件
//连边
if(x==0&&y==0){//假假
a_d(a+n,b);
a_d(b+n,a);
}
if(x==0&&y==1){//假真
a_d(a+n,b+n);
a_d(b,a);
}
if(x==1&&y==0){//真假
a_d(a,b);
a_d(b+n,a+n);
}
if(x==1&&y==1){//真真
a_d(a,b+n);
a_d(b,a+n);
}
}
for(int i=1;i<=2*n;i++)if(!d_f[i])t_j(i);//缩点
for(int i=1;i<=n;i++){//遍历所有的点
if(n_w[i]==n_w[i+n]){//和另一个条件在同一个环里
puts("IMPOSSIBLE");//无解
return 0;
}
}
puts("POSSIBLE");//有解
for(int i=1;i<=n;i++){//输出
//判断真假
if(n_w[i]<n_w[i+n])printf("1 ");
else printf("0 ");
}
return 0;
}
满汉全席
将每个材料分成两部分，分为满式和汉式（对应上面的两种对立关系）。
连边的时候仍然是一个强制实现不了另一个必须实现，tarjan 缩点，题目只问了能不能实现，所以更容易一些，判断一个材料会不会又是满式又是汉式即可。
多测清空！
代码
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<bitset>
#include<stack>
#include<map>
using namespace std;
long long r_r(){//快读
long long x=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
const int o_o=2e3+10;
int t,n,m;
//链式前向星
struct po{
int v,n_t;
}p_p[o_o];
int h_d[o_o],x_p;
int l_w[o_o],d_f[o_o];//时间戳
int x_x;//时间编号
int n_w[o_o];//新节点编号
int b_b[o_o];//标记在当前环中已经遍历过
int c_c;//新节点编号
int s_s[o_o],t_p;//存环上的点
char s_1[5],s_2[5];//评审员两个口味
void a_d(int u,int v){//加边
p_p[++x_p].n_t=h_d[u];
p_p[x_p].v=v;
h_d[u]=x_p;
}
void t_j(int k){//缩点
l_w[k]=d_f[k]=++x_x;
s_s[++t_p]=k;
b_b[k]=1;
for(int i=h_d[k];i;i=p_p[i].n_t){
int v=p_p[i].v;
if(!d_f[v]){
t_j(v);
l_w[k]=min(l_w[k],l_w[v]);
}else if(b_b[v])l_w[k]=min(l_w[k],d_f[v]);
}
if(l_w[k]==d_f[k]){//缩点
int v;
c_c++;
while(s_s[t_p+1]!=k){
v=s_s[t_p--];
b_b[v]=0;
n_w[v]=c_c;
}
}
}
void yv(){//初始化
x_p=x_x=c_c=0;
memset(h_d,0,sizeof(h_d));
memset(n_w,0,sizeof(n_w));
memset(l_w,0,sizeof(l_w));
memset(d_f,0,sizeof(d_f));
}
int main(){
t=r_r();
while(t--){
yv();//初始化
n=r_r();m=r_r();
for(int i=1;i<=m;++i){
scanf("%s%s",&s_1,&s_2);//读入两个爱好
int k_1=0,k_2=0;//分离数字
int k;//辅助下标
k=1;
while(isdigit(s_1[k]))k_1=(k_1<<1)+(k_1<<3)+(s_1[k++]^48);
k=1;
while(isdigit(s_2[k]))k_2=(k_2<<1)+(k_2<<3)+(s_2[k++]^48);
//分类连边
if(s_1[0]=='m'){
if(s_2[0]=='h'){
a_d(k_1+n,k_2+n);
a_d(k_2,k_1);
}else {
a_d(k_1+n,k_2);
a_d(k_2+n,k_1);
}
}else if(s_1[0]=='h'){
if(s_2[0]=='h'){
a_d(k_1,k_2+n);
a_d(k_2,k_1+n);
}else {
a_d(k_1,k_2);
a_d(k_2+n,k_1+n);
}
}
}
for(int i=1;i<=n<<1;++i)if(!d_f[i])t_j(i);//缩点
int b_p=0;
for(int i=1;i<=n;++i)
if(n_w[i]==n_w[i+n]){//自己和自己的对立在同一个强连通块中
b_p=1;//标记
break;
}
if(b_p)puts("BAD");//不能实现
else puts("GOOD");//可以实现
}
return 0;
}
