2 – SAT

2 – SAT 就是2判定性问题,是一种特殊的逻辑判定问题。

例,n对东西,每对只能选一个(i0i1),不能不选。即:A or _A = 1 , A xor _A = 1

还存在一些约束关系(i0,j0),表示i0不能跟j0一起选。那需连边

i0-> j1 如果选i0的话必须选j1

j0-> i1如果选j0的话必须选i1

表示了一种递推的关系:选哪个必选哪一个

一般题目给的都是一对一对的东西,二选一,不能不选。本身那几对东西是没有关系的,然后题目会定义一些规则,或者我们自己加入条件(如二分的参数),使对与对之间有了一些约束关系: 1)a必选b a->b

                   2)a必选 _a->a

       对这个新图求SCC,同一SCC的要么全选,要么都不选。

如果发现a,_a在同一SCC,表明矛盾了。

不矛盾的话,对缩点后的图按照自底向上选择一个还未被标记的点,标记选上,然后把它的对立点及其前代都删除。

选择一个点要把它及其所有后代都选上。不选一个点,要把它及其前代都不选。

算法流程:

1、建图,求SCC。若某一个点,a_a在同一个SCC,则无解,退出;

2、对求得的缩点,用原来的反图建一个DAG

3、TopoSort得到一个原图的自底向上的序列,点是缩点后的SCC,没必要原来的每个点;

4、从左往右,对整个序列的点,如果未标记删除,就标记选它,同时把这个SCC里的所有原来的点的对立点及其各自的后代(因为是反图)都标记删除;

5、重复上面过程,最后被标记选上的SCC内的点都是选择的点。其个数=n

虽然被删除的点也是n个,但是他们可能会存在冲突关系。而标记选上的点间是相容的。

 

挺多用二分的。对于二分设定的参数,可能建图时要考虑这个条件,如POJ 2749


/*
    POJ 2749 Building roads
    题意:给出n个牛棚、两个特殊点S1,S2的坐标。S1、S2直连。牛棚只能连S1或S2
           还有,某些牛棚只能连在同一个S,某些牛棚不能连在同一个S
           求使最长的牛棚间距离最小 距离是曼哈顿距离
    使最大值最小,二分的经典应用
    二分枚举最大值limit,然后重新构图,用2-SAT判定可行性
    用布尔变量Xi表示第i个牛棚连到S1,~Xi表示连到S2
    检查每一个约束条件,构图:
    1.hate关系的i,j  Xi->~Xj  ~Xi->Xj  Xj->~Xi  ~Xj->Xi
    2.friend关系的i,j  Xi->Xj  ~Xi->~Xj  Xj->Xi  ~Xj->~Xi
    接下来的也要检查,因为引入参数,就是多了约束条件了
    这四种情况就是i,j到达对方的所有情况了
    3.dist(i,S1)+dist(S1,j)>limit  Xi->~Xj  Xj->Xi
    4.dist(i,S2)+dist(S2,j)>limit  ~Xi->Xj  ~Xj->Xi
    5.dist(i,S1)+dist(S1,S2)+dist(S2,j)>limit Xi->Xj  ~Xj->~Xi
    5.dist(i,S2)+dist(S2,S1)+dist(S1,j)>limit ~Xi->~Xj  Xj->Xi
    然后求SCC 判断Xi与~Xi是否在同一个SCC中,是的话就有矛盾
*/

#include
<cstdio>
#include
<cstring>
#include
<algorithm>
#include
<vector>
using namespace std;
const int MAXN = 500;
const int INF = 1000000000;
int N,A,B;
struct Two
{
    
int x,y;
}
;
Two pt[MAXN
+10],s1,s2;
Two fre[MAXN
*2+10],hate[MAXN*2+10];
struct Graph
{
    vector
<int>G[2*MAXN+10],_G[2*MAXN+10];
    
int ID[MAXN*2+10],ord[MAXN*2+10];
    
int SCC;
    
void init(int n)
    
{
        
for(int i=1;i<=n;i++)
        
{
            G[i].clear();
            _G[i].clear();
        }

    }

    
void add(int a,int b)
    
{
        G[a].push_back(b);
        _G[b].push_back(a);
    }

    
void dfs1(int u)
    
{
        ID[u]
=1;
        
for(int i=0,size=_G[u].size();i<size;i++)
        
{
            
int v=_G[u][i];
            
if(!ID[v])dfs1(v);
        }

        ord[
++SCC]=u;
    }

    
void dfs2(int u)
    
{
        ID[u]
=SCC;
        
for(int i=0,size=G[u].size();i<size;i++)
        
{
            
int v=G[u][i];
            
if(!ID[v])dfs2(v);
        }

    }

    
void kosaraju()
    
{
        memset(ID,
0,sizeof(ID));
        SCC
=0;
        
for(int i=1;i<=2*N;i++)
        
{
            
if(!ID[i])dfs1(i);
        }

        memset(ID,
0,sizeof(ID));
        SCC
=0;
        
for(int i=2*N;i;i--)
        
{
            
if(!ID[ord[i]])
            
{
                SCC
++;
                dfs2(ord[i]);
//
            }

        }

    }


}
graph;
inline 
int dist(Two &a,Two &b)
{
    
return abs(a.x-b.x)+abs(a.y-b.y);
}

bool chk(int limit)
{
    graph.init(
2*N);
    
//build
    for(int i=1;i<N;i++)
        
for(int j=i+1;j<=N;j++)
        
{
            
//dist(i,s1)+dist(j,s1)>L i0->j1 j0->i1
            if(dist(pt[i],s1)+dist(pt[j],s1)>limit)
            
{
                graph.add(i,j
+N);
                graph.add(j,i
+N);
            }

            
//dist(i,s2)+dist(j,s2)>L i1->j0 j1->i0
            if(dist(pt[i],s2)+dist(pt[j],s2)>limit)
            
{
                graph.add(i
+N,j);
                graph.add(j
+N,i);
            }

            
//dist(i,s1)+dist(s1,s2)+dist(s2,j)>L i0->j0 j1->i1
            if(dist(pt[i],s1)+dist(s1,s2)+dist(s2,pt[j])>limit)
            
{
                graph.add(i,j);
                graph.add(j
+N,i+N);
            }

            
//dist(i,s2)+dist(s2,s1)+dist(s1,j)>L i1->j1 j0->i0
            if(dist(pt[i],s2)+dist(s2,s1)+dist(s1,pt[j])>limit)
            
{
                graph.add(i
+N,j+N);
                graph.add(j,i);
            }

        }

    
for(int i=1;i<=A;i++)
    
{
        
//i0->j1,i1->j0,j0->i1,j1->i0
        graph.add(hate[i].x,hate[i].y+N);
        graph.add(hate[i].x
+N,hate[i].y);
        graph.add(hate[i].y,hate[i].x
+N);
        graph.add(hate[i].y
+N,hate[i].x);
    }

    
for(int i=1;i<=B;i++)
    
{
        
//i0->j0,i1->j1,j0->i0,j1->i1
        graph.add(fre[i].x,fre[i].y);
        graph.add(fre[i].x
+N,fre[i].y+N);
        graph.add(fre[i].y,fre[i].x);
        graph.add(fre[i].y
+N,fre[i].x+N);
    }

    graph.kosaraju();
    
for(int i=1;i<=N;i++)
    
{
        
if(graph.ID[i]==graph.ID[i+N])return false;
    }

    
return true;
}

int main()
{
    
int Max;
    
while(~scanf("%d%d%d",&N,&A,&B))
    
{
        scanf(
"%d%d%d%d",&s1.x,&s1.y,&s2.x,&s2.y);
        
//Max = 0;
        for(int i=1;i<=N;i++)
        
{
            scanf(
"%d%d",&pt[i].x,&pt[i].y);
            
//Max = max(Max,dist(pt[i],s1));
            
//Max = max(Max,dist(pt[i],s2));
        }

        
//Max = 2*Max+dist(s1,s2)+1;
        for(int i=1;i<=A;i++)
            scanf(
"%d%d",&hate[i].x,&hate[i].y);
        
for(int i=1;i<=B;i++)
            scanf(
"%d%d",&fre[i].x,&fre[i].y);

        
int left = 0,right = INF;
        
while(right-left>1)
        
{
            
int mid = (right+left)>>1;
            
if(chk(mid))right=mid;
            
else left=mid;
        }
    
        
if(right==INF)puts("-1");
        
else printf("%d\n",right);
    }
        
    
return 0;
}




/*
POJ 2723 Get Luffy Out
    题意:给出N对钥匙,一对钥匙只能用一个 M个门,每个门上2个值,只要有其中一个值的钥匙即可开门了,问最大能开的门,门得按顺序开。
    既然是按顺序开,就可以二分枚举能开的门的个数
    然后用2-SAT判可行性
    建图方法为,对于门上的两个值a,b 显然有_a->b,_b->a
*/


/*
POJ 3678 Katu Puzzle
6个逻辑表达式,建图用
a  AND  b = 1      <==>  _a->a  _b->b
a  AND  b = 0       <==>  a->_b  b->_a
a  OR  b = 1        <==>  _a->b  _b->a
a  OR  b = 0        <==>  a->_a  b->_b
a  XOR b = 1        <==>  _a->b  a->_b  _b->a  b->_a
a  XOR b = 0        <==>  a->b  _a->_b  b->a  _b->_a
其实记住三个就够了,另外三个就两边取反就可以了
*/




/*
    POJ 3648 Wedding
    题意:n对夫妻,夫妻不能坐在同一排。m种通奸关系,有通奸关系的a,b不能同时坐在新娘的对面一排,求方案
    以新娘为参考系,x表示坐在新娘一侧,_x表示坐在对面一侧
    有通奸关系的a,b   有_a->b  _b->a
    最后!新娘一定要选上,所以连0h->0w 这样子连,拓扑排序后自底向上肯定会选上新娘
    缩点建图后再拓扑排序
    select的过程,遇到没有标记的块就选上它,并把它内所有点的对立点及其前代都标记删除
    最后删除掉的肯定是n个
    这里对反图建图,所以直接拓扑排序就可以自底向上了
*/

#include
<cstdio>
#include
<cstring>
#include
<vector>
#include
<queue>
using namespace std;
const int MAXN = 1000;
struct Graph
{
    vector
<int>G[MAXN*2+10],_G[MAXN*2+10];
    vector
<int>Dag[MAXN*2+10],inDag[MAXN*2+10];
    
int n,SCC;
    
int ID[MAXN*2+10],ord[MAXN*2+10];
    
int in[MAXN*2+10],pos[MAXN*2+10];
    
int color[MAXN*2+10];
    
void init(int nn)
    
{
        n
=nn;
        
for(int i=0;i<2*n;i++)
        
{
            G[i].clear();
            _G[i].clear();
        }

    }

    
void add(int u,int v)
    
{
        G[u].push_back(v);
        _G[v].push_back(u);
    }

    
void dfs1(int u)
    
{
        ID[u]
=1;
        
for(int i=0,size=_G[u].size();i<size;i++)
        
{
            
int v=_G[u][i];
            
if(ID[v]==-1)dfs1(v);
        }

        ord[SCC
++]=u;
    }

    
void dfs2(int u)
    
{
        ID[u]
=SCC;
        
for(int i=0,size=G[u].size();i<size;i++)
        
{
            
int v=G[u][i];
            
if(ID[v]==-1)dfs2(v);
        }

    }

    
void kosaraju()
    
{
        SCC 
= 0;
        memset(ID,
-1,sizeof(ID));    
        
for(int i=0;i<2*n;i++)
            
if(ID[i]==-1)dfs1(i);
        SCC 
= 0;
        memset(ID,
-1,sizeof(ID));    
        
for(int i=2*n-1;i>=0;i--)
            
if(ID[ord[i]]==-1)
            
{
                dfs2(ord[i]);
                SCC
++;
            }

    }

    
bool chk()
    
{
        
for(int i=0;i<2*n;i+=2)
            
if(ID[i]==ID[i+1])return false;
        
return true;
    }

    
void build_Dag()//对反图建DAG  这样topoSort就是自底向上的了
    {
        
for(int i=0;i<SCC;i++)
        
{
            Dag[i].clear();
            inDag[i].clear();
        }

        memset(
in,0,sizeof(in));
        
for(int u=0,v;u<2*n;u++)
        
{
            inDag[ID[u]].push_back(u);
            
for(int i=0,size=_G[u].size();i<size;i++)
            
{
                v
=_G[u][i];
                
if(ID[u]!=ID[v])
                
{
                    Dag[ID[u]].push_back(ID[v]);
                    
++in[ID[v]];
                }

            }

        }

    }

    
void topo_Sort()
    
{
        queue
<int>Q;
        
for(int i=0;i<SCC;i++)
            
if(in[i]==0)Q.push(i);
        
int cnt = 0;
        
while(!Q.empty())
        
{
            
int u=Q.front();Q.pop();
            pos[cnt
++]=u;
            
for(int i=0,size=Dag[u].size();i<size;i++)
            
{
                
int v=Dag[u][i];
                
if(--in[v]==0)Q.push(v);
            }

        }

    }

    
void setColor(int u)
    
{
        color[u]
=2;
        
for(int i=0,size=Dag[u].size();i<size;i++)
        
{
            
int v=Dag[u][i];
            
if(color[v]!=2)setColor(v);
        }

    }

    
void select()
    
{
        memset(color,
0,sizeof(color));
        
for(int i=0;i<SCC;i++)
        
{
            
int u=pos[i];
            
if(color[u]==0)
            
{
                color[u]
=1;//select
                for(int j=0,size=inDag[u].size();j<size;j++)//set every _v
                {
                    
int v=inDag[u][j]^1;
                    
if(color[ID[v]]==2)continue;
                    setColor(ID[v]);
                }

            }

        }

    }

    
void solve()
    
{
        build_Dag();
        topo_Sort();
        select();
        
for(int i=2;i<2*n;i++)
            
if(color[ID[i]]==1)printf("%d%c ",i/2,(i&1)?'h':'w');
        puts(
"");
    }


}
graph;

int main()
{
    
//freopen("in","r",stdin);
    int n,m,a,b;
    
char ca,cb;
    
while(scanf("%d%d",&n,&m),n)
    
{
        graph.init(n);
        
for(int i=0;i<m;i++)
        
{
            scanf(
"%d%c%d%c",&a,&ca,&b,&cb);
            a
=a*2+(ca=='h');
            b
=b*2+(cb=='h');
            
//_a->b _b->a
            graph.add(a^1,b);
            graph.add(b
^1,a);
        }

        
//0h->0w  0wife一定要选
        graph.add(1,0);
        graph.kosaraju();
        
if(!graph.chk())puts("bad luck");
        
else graph.solve();
    }

    
return 0;
}




 

还有2

POJ 3207 把线当成SAT的点

POJ 3683 wedding类似