POJ 3678 Katu Puzzle(2-SAT判断)-白红宇

POJ 3678 Katu Puzzle(2-SAT判断)

阅读量：4072 次

发布时间：2019-05-25

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

【题目链接】

【题目大意】

有一个有向图G（V，E），每条边e（a,b）上有一个位运算符op（AND， OR或XOR）和一个值c（0或1）。

问能不能在这个图上的每个点分配一个值X（0或1），使得每一条边e(a,b)满足 Xa op Xb = c

【思路】

每一个点上只能取0或者1，显然是2-SAT模型。

关键是怎样建边。

对于两个点a和 b， a有两个值a1=0，a2=1， b也有两个值 b1=0, b2=1.

那么枚举这两点的所有关系

（a1, b1）

（a1, b2）

（a2, b1）

（a2, b2）

然后根据位运算符看每个关系时符合条件还是不符合，如果不符合就说明这个关系时矛盾对，要添加两条边

假设是关系（a1，b1）矛盾，那么就要添加边 a1—>b2, b1—>a2即可。

依次类推。

【代码】

#include
   
     #include
    
     #include
     
      using namespace std;typedef long long int64;const int MAXN = 2010;const int VN   = MAXN*2;const int EN   = 4000010;int n, m;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 size;    int head[VN];    struct Edge{         int v, next;     }E[EN];}g;class Two_Sat{public:    bool check(const Graph&g, const int n){        scc(g, n);         for(int i=0; i