SPOJ_9939
这个题目可以用2-SAT做。
首先既然是2-SAT的问题的话，我们就要去找核心变量，然而B的每局的选择却是3个，石头（1）、剪子（2）、布（3），难道3-SAT？开玩笑，目前至少我没见过3-SAT的题目。仔细想一下，其实选择也就两个，因为A的选择是定的，而我们必须让A赢，因此B的选择实际上只有两个。
找到核心变量之后就是构图了，由于构图要稍复杂一些，就不直接用字母代替了，还是用一个实例来说明一下吧。
我们不妨一共3局，A出的分别是1、2、3，那么我们可以得到B的选择如下。
B1 1 2 1
B2 2 3 3
!B 3 1 2
其中B1、B2为B的两个选择，!B为B所不能选的。
现在假设M为2，分别为1 2 1、2 3 0，也就是说B的选择在第1局和第2局时必须不同，在第2局和第3局地选择必须相同。
首先我们建1 2 1这个要求的边。假设第1局选1的话，那么第2局选什么都无所谓的，因此没有必然的关系，所以第1局的1就不用连边了。假设第1局选2的话，那么第2局就一定要选3，这样就需要连一条左边的2到右边的3的有向边。同理，右边的2到左边的1也需要连一条有向边。
然后建2 3 0这个要求的边。假设第2局选2的话，就会发现第3局是选什么都不行的，因此第2局必然不能选2，因此我们需要连一条左边的2到左边的3的有向边，意思是如果第2局选了2那么第2局必然选3，这样在最后求可行解的时候就必然不会把2选入内，也就确保了第2局不会选2。假设第2局选3的话，那么显然第3局也必然选3，这样连一条左边的3到右边的3的有向边。同理，还需要连一条右边的1到右边的3的有向边，和一条右边的3到左边的3的有向边。
其实所有的边都按上面说的原理去构造就可以了。建完图之后的任务就轻松了，只需要tarjan求强连通分量、缩点，然后判断一下就可以了。
#include<stdio.h>
#include<string.h>
#define MAXD 20010
#define MAXM 80010
int e, first[MAXD], next[MAXM], v[MAXM], st[MAXD], A[MAXD];
int dfn[MAXD], low[MAXD], color[MAXD], s[MAXD], top, cnt, col, ins[MAXD];
int N, M;
void add(int a, int b)
{
v[e] = b;
next[e] = first[a];
first[a] = e;
e ++;
}
void init()
{
int i, j, a, b, k, x, y;
scanf("%d%d", &N, &M);
memset(first, -1, sizeof(first));
e = 0;
for(i = 0; i < N; i ++)
{
scanf("%d", &A[i]);
if(A[i] == 1)
{
st[2 * i] = 1;
st[2 * i ^ 1] = 2;
A[i] = 3;
}
else if(A[i] == 2)
{
st[2 * i] = 2;
st[2 * i ^ 1] = 3;
A[i] = 1;
}
else
{
st[2 * i] = 1;
st[2 * i ^ 1] = 3;
A[i] = 2;
}
}
for(i = 0; i < M; i ++)
{
scanf("%d%d%d", &a, &b, &k);
a --;
b --;
x = 2 * a;
y = 2 * b;
if(k)
{
if(st[x] != A[b])
{
if(st[x] == st[y])
add(x, y ^ 1);
else
add(x, y);
}
if(st[x ^ 1] != A[b])
{
if(st[x ^ 1] == st[y])
add(x ^ 1, y ^ 1);
else
add(x ^ 1, y);
}
if(st[y] != A[a])
{
if(st[y] == st[x])
add(y, x ^ 1);
else
add(y, x);
}
if(st[y ^ 1] != A[a])
{
if(st[y ^ 1] == st[x])
add(y ^ 1, x ^ 1);
else
add(y ^ 1, x);
}
}
else
{
if(st[x] == A[b])
add(x, x ^ 1);
else
{
if(st[x] == st[y])
add(x, y);
else
add(x, y ^ 1);
}
if(st[x ^ 1] == A[b])
add(x ^ 1, x);
else
{
if(st[x ^ 1] == st[y])
add(x ^ 1, y);
else
add(x ^ 1, y ^ 1);
}
if(st[y] == A[a])
add(y, y ^ 1);
else
{
if(st[y] == st[x])
add(y, x);
else
add(y, x ^ 1);
}
if(st[y ^ 1] == A[a])
add(y ^ 1, y);
else
{
if(st[y ^ 1] == st[x])
add(y ^ 1, x);
else
add(y ^ 1, x ^ 1);
}
}
}
}
void tarjan(int u)
{
int i;
dfn[u] = low[u] = ++ cnt;
s[top ++] = u;
ins[u] = 1;
for(i = first[u]; i != -1; i = next[i])
{
if(!dfn[v[i]])
{
tarjan(v[i]);
if(low[v[i]] < low[u])
low[u] = low[v[i]];
}
else if(ins[v[i]] && dfn[v[i]] < low[u])
low[u] = dfn[v[i]];
}
if(low[u] == dfn[u])
{
for(s[top] = -1; s[top] != u;)
{
top --;
ins[s[top]] = 0;
color[s[top]] = col;
}
col ++;
}
}
int judge()
{
int i;
for(i = 0; i < N; i ++)
if(color[2 * i] == color[2 * i ^ 1])
return 0;
return 1;
}
void solve()
{
int i, j, k;
col = cnt = top = 0;
memset(dfn, 0, sizeof(dfn));
memset(ins, 0, sizeof(ins));
for(i = 0; i < 2 * N; i ++)
if(!dfn[i])
tarjan(i);
if(judge())
printf("yes\n");
else
printf("no\n");
}
int main()
{
int t, tt;
scanf("%d", &t);
for(tt = 0; tt < t; tt ++)
{
init();
printf("Case #%d: ", tt + 1);
solve();
}
return 0;
}