题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4879
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std; const int maxn = ; struct Two_Sat
{
int n;
vector<int> G[maxn*];
bool mark[maxn*];
int s[maxn*],cnt; void init(int n)
{
this->n = n;
memset(mark,,sizeof(mark));
for(int i=; i<=n*; i++) G[i].clear();
} void add_clause(int u,int v,int flag,char symbol)
{
u = u* + flag;
v = v* + flag;
if(symbol == 'A')
{
if(flag)
{
G[u].push_back(v);
G[v].push_back(u);
G[u^].push_back(u);
G[v^].push_back(v);
}
else
{
G[u^].push_back(v);
G[v^].push_back(u);
}
}
else if(symbol == 'O')
{
if(flag)
{
G[u^].push_back(v);
G[v^].push_back(u);
}
else
{
G[u].push_back(v);
G[v].push_back(u);
G[u^].push_back(u);
G[v^].push_back(v);
}
}
else
{
if(flag)
{
G[u^].push_back(v);
G[v].push_back(u^);
G[v^].push_back(u);
G[u].push_back(v^);
}
else
{
G[u].push_back(v);
G[v].push_back(u);
G[u^].push_back(v^);
G[v^].push_back(u^);
}
}
} bool dfs(int u)
{
if(mark[u^]) return false;
if(mark[u]) return true;
mark[u] = true;
s[cnt++] = u;
for(int i=; i<G[u].size(); i++)
{
if(!dfs(G[u][i])) return false;
}
return true;
} bool solve()
{
for(int i=; i<n*; i+=)
{
if(!mark[i] && !mark[i+])
{
cnt = ;
if(!dfs(i))
{
while(cnt>) mark[s[--cnt]] = false;
if(!dfs(i+)) return false;
}
}
}
return true;
}
} solver; int main()
{
//freopen("E:\\acm\\input.txt","r",stdin);
int N; while(cin>>N)
{
int b[][];
bool ans = true;
for(int i=; i<N; i++)
for(int j=; j<N; j++)
scanf("%d",&b[i][j]); for(int i=; i<N; i++)
for(int j=i; j<N; j++)
{
if(i == j && b[i][j] != )
{
ans = false;
break;
}
if(b[i][j] != b[j][i])
{
ans = false;
break;
}
}
if(!ans)
{
printf("NO\n");
continue;
}
for(int k=; k<; k++)
{
solver.init(N);
for(int i=; i<N; i++)
for(int j=i+; j<N; j++)
{
char symbol;
if(i% == && j% == ) symbol = 'O';
else if(i% == && j% == ) symbol = 'A';
else symbol = 'X'; if(b[i][j] & (<<k))
solver.add_clause(i,j,,symbol);
else
solver.add_clause(i,j,,symbol); }
if(!solver.solve())
{
ans = false;
break;
}
}
if(ans) printf("YES\n");
else printf("NO\n");
}
}