算法：ZOJ 3656 Bit Magic （2-SAT判断）

算法：ZOJ 3656 Bit Magic （2-SAT判断）2014-01-10 csdn shuangde800【题目大意】

假设已经知道一个数组a[N]，那么用一下函数生成一个矩阵b：

void calculate（int a[N], int b[N][N]） {
for （int i = 0; i < N; ++i） {
for （int j = 0; j < N; ++j） {
if （i == j） b[i][j] = 0;
else if （i % 2 == 1 && j % 2 == 1） b[i][j] = a[i] | a[j];
else if （i % 2 == 0 && j % 2 == 0） b[i][j] = a[i] & a[j];
else b[i][j] = a[i] ^ a[j];
}
}
}

现在已知一个矩阵b，问存不存在一个数组a能转换为矩阵b？

【分析】

这题其实就是 POJ 3678 Katu Puzzle 的加强版。

poj3678每个数字只能选择0或者1，相当与一个二进制只有1位的整数。

而这题每个数字的范围是0 ≤ b[i][j] ≤ 2 ^ 31 - 1，相当于是二进制有31位的整数，那么只要枚举二进制位，分别对每个二进制为进行2-SAT判断即可！

【代码】

#include<iostream> #include<cstdio>#include<cstring>using namespace std;typedef long long int64;const int MAXN = 610;const int VN = MAXN*62;const int EN = 2000010;int n;int mat[MAXN][MAXN];struct Graph{int size;int head[VN];struct Edge{int v, next; }E[EN];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++;}}g;class Two_Sat{public:bool check（const Graph&g, const int n）{scc（g, n）; for（int i=0; i<n; ++i）if（belong[i*2] == belong[i*2+1]）return false;return true;}private:void tarjan（const Graph&g, const int u）{int v;DFN[u] = low[u] = ++idx;sta[top++] = u;instack[u] = true;for（int e=g.head[u]; e！=-1; e=g.E[e].next）{v = g.E[e].v;if（DFN[v] == -1）{tarjan（g, v）;low[u] = min（low[u], low[v]）;}else if（instack[v]）{low[u] = min（low[u], DFN[v]）;}}if（low[u] == DFN[u]）{++bcnt;do{v = sta[--top];instack[v] = false;belong[v] = bcnt;}while（u ！= v）;}}void scc（const Graph& g, const int n）{top = idx = bcnt = 0;memset（DFN, -1, sizeof（DFN））;memset（instack, 0, sizeof（instack））;for（int i=0; i<2*n; ++i）if（DFN[i] == -1）tarjan（g, i）;}private:int top, idx, bcnt;int DFN[VN];int low[VN];int sta[VN];int belong[VN];bool instack[VN];}sat;bool ok（）{for（int i=0; i<n; ++i）{if（mat[i][i] ！= 0） return false;for（int j=i+1; j<n; ++j）if（mat[i][j] ！= mat[j][i]）return false;}return true;}bool judge（）{// 枚举二进制位for（int k=0; k<31; ++k）{g.init（）;for（int i=0; i<n; ++i）{for（int j=i+1; j<n; ++j）{int u=i, v=j, w=（mat[i][j]>>k）&1;if（i%2==0 && j%2==0）{if（w）{g.addEdge（u*2, v*2+1）,g.addEdge（v*2, u*2+1）; //0, 0 g.addEdge（u*2, v*2）,g.addEdge（v*2+1, u*2+1）; // 0, 1g.addEdge（u*2+1, v*2+1）,g.addEdge（v*2, u*2）; // 1, 0}else{g.addEdge（u*2+1, v*2）,g.addEdge（v*2+1, u*2）; // 1, 1 }}else if（i%2==1 && j%2==1）{if（w）{g.addEdge（u*2, v*2+1）,g.addEdge（v*2, u*2+1）; //0, 0 }else{g.addEdge（u*2, v*2）,g.addEdge（v*2+1, u*2+1）; // 0, 1g.addEdge（u*2+1, v*2+1）,g.addEdge（v*2, u*2）; // 1, 0g.addEdge（u*2+1, v*2）,g.addEdge（v*2+1, u*2）; // 1, 1 }}else{ // XORif（w）{g.addEdge（u*2, v*2+1）,g.addEdge（v*2, u*2+1）; //0, 0 g.addEdge（u*2+1, v*2）,g.addEdge（v*2+1, u*2）; // 1, 1 }else{g.addEdge（u*2, v*2）,g.addEdge（v*2+1, u*2+1）; // 0, 1g.addEdge（u*2+1, v*2+1）,g.addEdge（v*2, u*2）; // 1, 0}}}}if（！sat.check（g, n）） return false;}return true;}int main（）{while（~scanf（"%d", &n））{g.init（）;bool flag = true;for（int i=0; i<n; ++i）for（int j=0; j<n; ++j）scanf（"%d", &mat[i][j]）;if（！ok（））{puts（"NO"）;continue;} if（judge（）） puts（"YES"）;else puts（"NO"）;}return 0;}