ZOJ 3656 Bit Magic(2-SAT判定)
4961 ワード
【テーマリンク】
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3656
【タイトルの大意】
配列a[N]を知っていると仮定して、行列bを関数で生成します。
この問題は実はです POJ 3678 Katu Puzle の強化版です
poj 3678数字は0または1しか選択できません。バイナリと同じ1ビットの整数に相当します。
この問題の数字の範囲は0≦b[i][j]≦2^31-1で、 このように、バイナリは31ビットの整数を持っています。バイナリビットを列挙すれば、それぞれ2-SATの判断を行うことができます。
【コード】
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3656
【タイトルの大意】
配列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 Puzle の強化版です
poj 3678数字は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, 1
g.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, 1
g.addEdge(u*2+1, v*2+1), g.addEdge(v*2, u*2); // 1, 0
g.addEdge(u*2+1, v*2), g.addEdge(v*2+1, u*2); // 1, 1
}
}else{ // XOR
if(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, 1
g.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;
}