思路:我们需要判断是否有满足的a[n],其实也就是对每一个二进制位进行判断,看是否有满足的。那么我们每次取出一个二进制位,这样每一位只有0,1两种状态,就成了比较典型的2-SAT问题了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define Maxn 1010
#define Maxm Maxn*Maxn
using namespace std;
int vi[Maxn],head[Maxn],dfn[Maxn],low[Maxn],e,n,lab,top,num,m,id[Maxn],Stack[Maxn],B[][];
struct Edge{
int u,v,next;
}edge[Maxm];
void init()//初始化
{
memset(vi,,sizeof(vi));
memset(head,-,sizeof(head));
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
memset(id,,sizeof(id));
e=lab=top=num=;
}
void add(int u,int v)//加边
{
edge[e].u=u,edge[e].v=v,edge[e].next=head[u],head[u]=e++;
}
void Tarjan(int u)//找出强连通分支
{
int i,j,v;
//cout<<u<<endl;
dfn[u]=low[u]=++lab;
Stack[top++]=u;
vi[u]=;
for(i=head[u];i!=-;i=edge[i].next)
{
v=edge[i].v;
if(!dfn[v])
{
Tarjan(v);
low[u]=min(low[u],low[v]);
}
if(vi[v])
low[u]=min(low[u],dfn[v]); }
if(low[u]==dfn[u])
{
++num;
do{
i=Stack[--top];
vi[i]=;
id[i]=num;
}while(i!=u);
}
}
int Ok()
{
int i,j;
for(i=;i<n;i++)
for(j=i+;j<n;j++)
{
if(i==j&&(B[i][j]!=||B[j][i]!=))
return ;
if(B[i][j]!=B[j][i])
return ;
}
return ;
}
void buildGraphic(int k)
{
int i,j,temp;
for(i=;i<n-;i++)
for(j=i+;j<n;j++)
{
if(i%==&&j%==)
{
temp=(<<k);
if(B[i][j]&temp)
{
add(i,j+n);
add(j,i+n);
}
else
{
add(i+n,j);
add(j+n,i);
add(i,j);
add(j,i);
add(i+n,j+n);
add(j+n,i+n);
}
}
else
if(i%==&&j%==)
{
temp=(<<k);
if(B[i][j]&temp)
{
add(i,j+n);
add(j,i+n);
add(i,j);
add(j,i);
add(i+n,j+n);
add(j+n,i+n);
}
else
{
add(i+n,j);
add(j+n,i);
}
}
else
{
temp=(<<k);
if(B[i][j]&temp)
{
add(i,j+n);
add(j,i+n);
add(i+n,j);
add(j+n,i);
}
else
{
add(i,j);
add(j,i);
add(i+n,j+n);
add(j+n,i+n);
}
}
}
}
int solve(int k)
{
int i,j;
buildGraphic(k);
for(i=;i<*n;i++)
{
if(!dfn[i])
Tarjan(i);
}
for(i=;i<n;i++)
{
if(id[i]==id[i+n])
return ;
}
return ;
}
int main()
{
int i,j;
while(scanf("%d",&n)!=EOF)
{
for(i=;i<n;i++)
for(j=;j<n;j++)
scanf("%d",&B[i][j]);
if(!Ok())
{
printf("NO\n");
continue;
}
int k;
for(k=;k<=;k++)//每次取出一个二进制位,进行2-SAT判定
{
init();
if(!solve(k))
break;
}
if(k<=)
printf("NO\n");
else
printf("YES\n");
}
return ;
}
05-11 10:48