题意
Alice和Bob玩n次剪刀石头布游戏
在这里，1代表石头，2代表布，3代表剪刀
Alice知道Bob每次出什么，为了公平他让Bob制订了m条规则
每条规则是第a轮次和第b轮次Alice必须出相同（或者不同）的手势
问Alice是否可以遵守规则之下每一轮次都不输给Bob
分析
对于bob每次出招，Alice都只能有两种状态，平局或者赢，由此构成2-SAT
如果2-SAT无解说明Alice如果遵循规则则至少要输一次
如果2-SAT有解但是某个解是所有轮次平局，那Alice还能赢吗
这时候我们把（1,2,3）置换成（2,3,1），Alice就美滋滋的n战n胜了
所以如果2-SAT有解，则Alice一定可以赢
其实题意说平局也算Alice赢的啦
如何构图呢
如果要求第a轮和第b轮相同，而a平和b赢不同，则加边（a平，b平），（b赢，a赢）
如果要求第a轮和第b轮不同，而a平和b赢相同，则加边（a平，b平），（b赢，a赢）
貌似只要考虑这两类矛盾就可以（ac）了？
下面的操作是正确的，但是不加也可以ac
如果要求第a轮和第b轮相同，而a_i和a_j相同，则加边（a_i,a_j），（a_j,a_i）
emmm貌似过度分类讨论所有细节有时候不太简洁呢
代码
#include <cstdio>
#include <cstring>
#define MAX 1000007
#define MAXN 20007
#define MAXM 20007
using namespace std;
typedef long long LL;
struct Edge{int to,next;}edge[MAXM];
int head[MAXN],tot;
int Low[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN];
int Index,top;
int scc;
bool Instack[MAXN];
int num[MAXN];
void addEdge(int u,int v) {
edge[tot].to=v;
edge[tot].next=head[u];
head[u]=tot++;
}
void addEdge(int u,int v,int x,int y){
addEdge(u,v);
addEdge(x,y);
}
void Tarjan(int u) {
int v;
Low[u]=DFN[u]=++Index;
Stack[top++]=u;
Instack[u]=true;
for(int i=head[u];i!=-1;i=edge[i].next){
v=edge[i].to;
if(!DFN[v]){
Tarjan(v);
if(Low[u]>Low[v])Low[u]=Low[v];
}
else if(Instack[v]&&Low[u]>DFN[v])
Low[u]=DFN[v];
}
if(Low[u]==DFN[u]){
scc++;
do{
v=Stack[--top];
Instack[v]=false;
Belong[v]=scc;
num[scc]++;
}while(v!=u);
}
}
bool solve(int N) {
memset(DFN,0,sizeof DFN);
memset(Instack,false,sizeof Instack);
memset(num,0,sizeof num);
Index=scc=top=0;
for(int i=1;i<=N;i++)
if(!DFN[i])Tarjan(i);
int n=N/2;
for(int i=1;i<=n;i++){
if(Belong[i]==Belong[i+n])return false;
}
return true;
}
void init() {
tot=0;
memset(head,-1,sizeof head);
}
int bob[MAXN],cas,n,m,a,b,k,x,beat[4]={0,2,3,1};
int main(){
scanf("%d",&cas);
for(int ccc=1;ccc<=cas;ccc++){
init();
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&x);
bob[i]=x;
bob[i+n]=beat[x];
}
for(int i=1;i<=m;i++){
scanf("%d%d%d",&a,&b,&k);
if(k==0){
if(bob[a]!=bob[b]){
addEdge(a,b+n,b,a+n);
}
if(bob[a]!=bob[b+n]){
addEdge(a,b,b+n,a+n);
}
if(bob[a+n]!=bob[b]){
addEdge(a+n,b+n,b,a);
}
if(bob[a+n]!=bob[b+n]){
addEdge(a+n,b,b+n,a);
}
}
else{
if(bob[a]==bob[b]){
addEdge(a,b+n,b,a+n);
}
if(bob[a]==bob[b+n]){
addEdge(a,b,b+n,a+n);
}
if(bob[a+n]==bob[b]){
addEdge(a+n,b+n,b,a);
}
if(bob[a+n]==bob[b+n]){
addEdge(a+n,b,b+n,a);
}
}
}
printf("Case #%d: ",ccc);
printf(solve(n*2)?"yes
":"no
");
}
return 0;
}