ZOJ 3656 Bit Magic(2-sat)
3300 ワード
标题:b[]]の値をあげて、a[]を出す値が存在するかどうかを返します..
考え方:2-sat、他の人が2-satで私がやったと言っているのを見て、試合になると必ず2-satを使うことができるとは限らない.そして、整数32位のバイナリ数は、一人一人が考えなければならない.mleはできない.他人のブログを見て作った.葛藤しますね.試合はどうしますか.の
考え方:2-sat、他の人が2-satで私がやったと言っているのを見て、試合になると必ず2-satを使うことができるとは限らない.そして、整数32位のバイナリ数は、一人一人が考えなければならない.mleはできない.他人のブログを見て作った.葛藤しますね.試合はどうしますか.の
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
const int N = 509*39*2;
int n;
int re[509][509];
bool judge()
{
for(int i=0;i<n;i++)
if(re[i][i]) return false;
for(int i=0;i<n;i++)
for(int j=0;j<i;j++)
if(re[i][j]!=re[j][i]) return false;
return true;
}
int dfn[N],low[N],col[N],post[N],ind,color;
struct LT{
int to,nex;
}L[501*501*2];
int F[N],cnt;
void add(int f,int t)
{
L[cnt].to = t;
L[cnt].nex = F[f];
F[f] = cnt++;
}
void op0(int a,int b,int k,int i)///&
{
if(k&(1<<i))
{
add(a*32+i+n,a*32+i);
add(b*32+i+n,b*32+i);
}else
{
add(a*32+i,b*32+i+n);
add(b*32+i,a*32+i+n);
}
}
void op1(int a,int b,int k,int i)///|
{
if(k&(1<<i))
{
add(a*32+i+n,b*32+i);
add(b*32+i+n,a*32+i);
}else
{
add(a*32+i,a*32+i+n);
add(b*32+i,b*32+i+n);
}
}
void op2(int a,int b,int k,int i)///^
{
if(k&(1<<i))
{
add(a*32+i,b*32+i+n);
add(a*32+i+n,b*32+i);
add(b*32+i,a*32+i+n);
add(b*32+i+n,a*32+i);
}else
{
add(a*32+i,b*32+i);
add(a*32+i+n,b*32+i+n);
add(b*32+i,a*32+i);
add(b*32+i+n,a*32+i+n);
}
}
int S[N],st;
void tdfs(int k)
{
dfn[k] = low[k] = ++ind;
post[k] = 1;S[st++] = k;
for(int i=F[k];i;i=L[i].nex)
{
int to =L[i].to;
if(!dfn[to])
{
tdfs(to);
low[k] = min(low[k],low[to]);
}else if(post[k]&&low[k]>dfn[to])
low[k] = dfn[to];
}
if(dfn[k]==low[k]){
int i;color++;
for(i=S[--st];i!=k;i=S[--st])
{
post[i] = 0;col[i] =color;
}post[k] = 0;col[k] = color;
}
}
bool tarjan()
{
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(col,0,sizeof(col));
ind = 0,color=0;
for(int i=0;i<n*32*2;i++)
if(!dfn[i]) st=0,tdfs(i);
for(int i=0;i<n*32;i++)
if(col[i]==col[i+n]) return false;
return true;
}
void solve()
{
for(int k=0;k<31;k++)
{ cnt = 1;
memset(F,0,sizeof(F));
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
if(i%2==1&&j%2==1)
op1(i,j,re[i][j],k);
else if(i%2==0&&j%2==0)
op0(i,j,re[i][j],k);
else op2(i,j,re[i][j],k);
}
}
if(!tarjan()){
printf("NO
");return ;
}
}
printf("YES
");
}
int main()
{
freopen("in.txt","r",stdin);
while(~scanf("%d",&n))
{
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
scanf("%d",&re[i][j]);
if(!judge())
{
printf("NO
");
continue;
}
solve();
}
return 0;
}