本文共 1044 字，大约阅读时间需要 3 分钟。

【题目大意】

Bob和Alice玩剪刀石头布，一个玩n轮，Alice已经知道了Bob每次要出什么，1代表剪刀，2代表石头，3代表布，然后Bob对Alice作出了一些限制：

给m行，每行是a b k，如果k是0，表示Alice第a次和b次出的拳必须相同，如果k是1，表示Alice第a次和b次出的拳必须不相同。

一但Alice破坏了这个限制规则，或者输了一局，那么Alice就彻底输了。

问Alice可不可能赢？

【分析】

因为Alice一次都不能输，所以根据Bob出的拳，Alice只可以赢或者平局，即每次有两种选择，是2-SAT模型

然后会有一些矛盾对，假设第a次可以出a1，a2， 第b次可以出b1和b2

如果第a次和b次要求相同， 但是a1和b1不同，说明这个矛盾，建立连接 a1—>b2, b1—>a2

同理，第a次和b次要求不相同，但是a1和b2相同，说明这个矛盾，建立链接a1—>b1,  b2—>a2

……

然后用2-SAT判断即可

【代码】

#include
   
     #include
    
     #include
     
      using namespace std;typedef long long int64;const int MAXN = 10010;const int VN = MAXN*2;const int EN = VN*3;int n, m;int pat[MAXN];int alice[MAXN][2];struct Edge{    int v, next;};class Graph{public:     void init(){        size = 0;        memset(head, -1, sizeof(head));    }    void addEdge(int u, int v){        E[size].v = v;        E[size].next = head[u];        head[u] = size++;    }public:    int head[VN];    Edge E[EN];private:    int size;}g;class Two_Sat{public:     bool check(const Graph&g, const int n){        scc(g, n);         for(int i=0; i
     
    
   

转载地址：http://ypzni.baihongyu.com/