2-sat问题，一种在两种可能性中选择必然关系的问题。
推荐两篇论文，也是学2-sat公认比较好的材料。前者较好理解，后者需耐心看。
http://bbs.byr.cn/wForum/boardcon.php?bid=212&id=15890&ftype=3&ap=278
“最小值尽量大”问题，又是一种经典模型，二分答案，从而判断是否能构建出合适的方案。
代码看书码的，注意几点：
不能缩点，会把不成立的情况缩掉，所以改为标记。
一旦任意一点的两种可能性都不成立，即不存在完整的方案。
本题只是二选一，A或B的一种形式来建边的，其他形式的2-sat要通过做题去接触，不过，总的来说都是根据必然关系建图。
#include<stdio.h>
#include<string.h>
#include<vector>
#include<stdlib.h>
#include<algorithm>
using namespace std; const int MAXN=; int T[MAXN][],n;
bool mark[MAXN<<];
int S[MAXN<<],c;
vector<int >G[MAXN<<]; void init(int n)
{
for(int i=;i<(n<<);i++)
G[i].clear();
memset(mark,,sizeof(mark));
} void add(int x,int xval,int y,int yval)
{
x=(x<<)+xval;
y=(y<<)+yval;
G[x].push_back(y^);
G[y].push_back(x^);
} bool dfs(int x)
{
if(mark[x^])
return false;
if(mark[x])
return true;
S[c++]=x;
mark[x]=true;
for(int i=;i<G[x].size();i++)
if(!dfs(G[x][i]))
return false;
return true;
} bool solve()
{
for(int i=;i<(n<<);i+=)
{
if(!mark[i]&&!mark[i+]){
c=;
if(!dfs(i)){
while(c>)
mark[S[--c]]=false;
if(!dfs(i+))
return false;
}
}
}
return true;
} int test(int p)
{
init(n);
for(int i=;i<n;i++)
for(int a=;a<;a++)
for(int j=i+;j<n;j++)
for(int b=;b<;b++)
if(abs(T[i][a]-T[j][b])<p)
add(i,a,j,b);
return solve();
} int main()
{
while(~scanf("%d",&n))
{
int l,r;
l=r=;
for(int i=;i<n;i++)
{
for(int j=;j<;j++)
{
scanf("%d",&T[i][j]);
r=max(r,T[i][j]);
}
}
while(l<r)
{
int m=l+(r-l+)/;
if(test(m))
l=m;
else
r=m-;
}
printf("%d\n",l);
}
return ;
}