转载请注明出处：http://blog.csdn.net/u013912596

题目大意：

Alice和Bob玩若干轮石头剪刀布的游戏，Alice已经知道了Bob在每一轮会出什么，但是Bob会给出一些Alice的限制条件，问Alice在不打破这些限制的情况下，有没有可能赢。

 限制格式为(i,j,w)，i,j代表第几轮，w=1的话，要求Alice在第i轮和第j轮的策略不能相同，w=0的话，要求Alice在第i轮和第j轮的策略必须相同。

思路：

a[i]=2时，Alice只能选择2,3，令此时的2为true，3为false。

a[i]=3时，Alice只能选择3,1，令此时的1为true，3为false。

可能有的同学会说，这不是有的矛盾了吗。。。（博主是蒟蒻。。当时也在纠结这个问题。。），后来发现其实没有影响，只是表示这两种状态而已，只要一开始定好规则，按照这个规则建边就好了。

好！下面开始认真的建边了！

对每条限制条件进行处理（Ai,Aj表示Alice在该轮的状态，true or false）：

1.当a[i]==a[j]，(1).w==1（不同）：Ai xor Aj =1

   (2).w==0（相同）：Ai xor Aj =0

2.当a[i]==1&&a[j]==2时，(1).w==1（不同）：Ai or ~Aj =1

   (2).w==0（相同）：~Ai and Aj =1（这个地方做得时候和上一条建边高反了T.T，结果调了一天。。。泪面。。）

3.当a[i]==2&&a[j]==3时，(1).w==1（不同）：~Ai or ~Aj =1

   (2).w==0（相同）：Ai and Aj =1

4.当a[i]==1&&a[j]==3时，(1).w==1（不同）：Ai or Aj =1

   (2).w==0（相同）：~Ai and ~Aj =1

好！有上述条件之后，我们就可以开始建边啦~（如果a[i]==2,a[j]==1什么的，交换一下 i , j 就好啦）下面是各个公式对应的建边方式：

把每个值是1(a)和0(~a)为两种状态，分清楚各种操作的本质就很简单了

AND 结果为1：建边 ~x->x,~y->y （两个数必须全为1）

AND 结果为0：建边 y->~x,x->~y （两个数至少有一个为0）

OR 结果为1：建边 ~x->y,~y->x （两个数至少有一个为1）

OR 结果为0：建边 x->~x,y->~y （两个数必须全为0）

XOR 结果为1：建边 x->~y,y->~x,~y->x,~x->y （两个数必须不同）

XOR 结果为0：建边 x->y,y->x,~x->~y,~y->~x （两个数必须相同）

好吧。。这道题建完边，用模板跑一边，结果就出来了，挺简单的。

代码：

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
int V;//mind assign
const int MAX_V=22222;
vector<int> G[MAX_V];
vector<int> rG[MAX_V];
vector<int> vs;
bool used[MAX_V];
int cmp[MAX_V];
int a[MAX_V];
void add_edge(int from,int to){
    G[from].push_back(to);
    rG[to].push_back(from);
}
void dfs(int v){
    used[v]=true;
    for(int i=0;i<G[v].size();i++){
        if(!used[G[v][i]]) dfs(G[v][i]);
    }
    vs.push_back(v);
}
void rdfs(int v,int k){
    used[v]=true;
    cmp[v]=k;
    for(int i=0;i<rG[v].size();i++)
        if(!used[rG[v][i]]) rdfs(rG[v][i],k);
}
int scc(){
    memset(used,0,sizeof(used));
    vs.clear();
    for(int v=0;v<V;v++){
        if(!used[v]) dfs(v);
    }
    memset(used,0,sizeof(used));
    int k=0;
    for(int i=vs.size()-1;i>=0;i--){
        if(!used[vs[i]]) rdfs(vs[i],k++);
    }
    return k;
}
int main()
{
    #ifndef ONLINE_JUDGE
        freopen("D:/in.txt","r",stdin);
        //freopen("D:/out.txt","w",stdout);
    #endif // ONLINE_JUDGE
    int T;scanf("%d",&T);
    int cas=1;
    while(T--){
        for(int i=0;i<MAX_V;i++) G[i].clear();
        for(int i=0;i<MAX_V;i++) rG[i].clear();
        memset(cmp,0,sizeof(cmp));
        int n,m;
        printf("Case #%d: ",cas++);
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++){
            scanf("%d",a+i);
        }
        V=2*n;
        for(int k=1;k<=m;k++){
            int i,j,w;
            scanf("%d%d%d",&i,&j,&w);
            i--;j--;

            if(a[i]==a[j]){
                if(w==1){
                    add_edge(i,j+n);
                    add_edge(j,i+n);
                    add_edge(i+n,j);
                    add_edge(j+n,i);
                }else{
                    add_edge(i,j);
                    add_edge(j,i);
                    add_edge(i+n,j+n);
                    add_edge(j+n,i+n);
                }
            }else{
                if(a[i]+a[j]==3){
                    if(a[i]!=1) swap(i,j);//这里必须要交换保证顺序正确
                    if(w==1){
                        add_edge(i+n,j+n);
                        add_edge(j,i);
                    }else{
                        add_edge(i,i+n);
                        add_edge(j+n,j);
                    }
                }else if(a[i]+a[j]==4){
                    //if(a[i]!=1) swap(i,j);//这里可以不用交换，因为操作一样
                    if(w==1){
                        add_edge(i,j+n);
                        add_edge(j,i+n);
                    }else{
                        add_edge(i+n,i);
                        add_edge(j+n,j);
                    }
                }else{
                    //if(a[i]!=2) swap(i,j);//同上
                    if(w==1){
                        add_edge(i+n,j);
                        add_edge(j+n,i);
                    }else{
                        add_edge(i,i+n);
                        add_edge(j,j+n);
                    }
                }
            }
        }
        //after build edges
        scc();

        bool isCon=false;
        for(int i=0;i<n;i++){
            if(cmp[i]==cmp[n+i]){
                printf("no\n");
                isCon=true;
                break;
            }
        }
        if(isCon) continue;
        printf("yes\n");
    }
    return 0;
}

HDU 4115 Eliminate the Conflict【2-sat】