这两天学习了一下2-SAT，主要参考了以下两个资料：

　　　　　

　　　　　

　　另外还有我觉得讲得挺白话的。

建图：

　　2-SAT问题远没有网络流那样复杂，只要抓住关系建好图基本就直接可以解了，在这类问题中建边的规则就是“必须”，对于边<i，j>，它的意义就是选择了i就必须选j。

　　对于题目中给出的每对关系都可以化成下面的几种形式：

　　　A,B不能同时取　　<A,B'><B,A'>

　　　A,B不能都不取　　<A',B><B',A>

　　　A,B必须都取或者都不取　　<A,B><B,A><A',B'><B',A'>

　　　必须取A　　<A',A>

　　主要的模型就这四个，其余的都可以通过徳摩根律化成上面的形式，前三个的建图都不难理解，对于第四个，这样建边是因为如果选了A'就必须选A,显然是不符合逻辑的，也就是说A'不可选，那么自然要选择A了。

 

算法

　　两种解法，第一种就是在图上直接暴力，递归+回溯来找可行解，时间复杂度O(n*m),这个算法比较慢，但是也不是毫无用武之地，如果要求字典序最小或者什么别的特殊要求的解的话，那么只能这样暴力枚举了。

　　如果仅仅是构造一个可行解的话，那么用论文里给的办法就行，也就是强连通缩点，然后判不相容的两个点是不是在一个连通分支。然后对新图边取反拓扑排序，每次把未染色的连通分支及和它对立的连通分支染色。至于为什么这么做，我还没有彻底明白，有待思考

入门练习

　　2-SAT本身就是个判定性问题，最基本的题型就是给定一些关系然后判定是否可解什么的，当然很多时候还会套上别的东西，一般的就是二分枚举答案+2-SAT判定是否有解。

　　还有一类就是在判定可解性之后，构造一个可行性方案。

pku 3207

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #define N 1010 6 using namespace std; 7 struct Edge{ 8     int u,v,next; 9     Edge(){}10     Edge(int _u,int _v,int _next){11         u=_u;v=_v;next=_next;12     }13 }edge[N*N];14 int dfn[N],low[N],id[N],stack[N*N],cc;15 int head[N],cnt,dep,top;16 int n,m;17 bool instack[N];18 void init(){19     memset(head,-1,sizeof(head));20     memset(instack,0,sizeof(instack));21     cnt=0;22 }23 void addedge(int u,int v){24     edge[cnt]=Edge(u,v,head[u]);head[u]=cnt++;25 }26 void tarjan(int u){27     int v;28     dfn[u]=low[u]=++dep;29     stack[++top]=u;30     instack[u]=1;31     for(int k=head[u];k!=-1;k=edge[k].next){32         v=edge[k].v;33         if(!dfn[v]){34             tarjan(v);35             low[u]=min(low[u],low[v]);36         }else if(instack[v])37             low[u]=min(low[u],dfn[v]);38     }39     if(dfn[u]==low[u]){40         ++cc;41         do{42             v=stack[top--];43             instack[v]=0;44             id[v]=cc;45         }while(v!=u);46     }47 }48 void solve(){49     dep=cc=top=0;50     memset(dfn,0,sizeof(dfn));51     for(int i=1;i<=2*m;i++)52         if(!dfn[i])tarjan(i);53 }54 int seg[N][2];55 bool check(int i,int j){56     return seg[i][0]
          
           
          
         
        
       
      

 

pku 3683

 

 

pku 3678

 

pku 3648

1 /*  2     建边规则：
      
       表示如果x在新娘对面，那么y必须也在新娘对面。  3     最后在新娘新郎之家建一条边表示新郎必须和新娘相对。  4     输出方案的时候要判断该点颜色是否和新娘的一致。  5 */  6   7 #include
       
          8 #include
        
           9 #include
         
           10 #include
          
            11 #include
           
             12 #define N 110 13 using namespace std; 14 struct Edge{ 15 int u,v,next; 16 Edge(){} 17 Edge(int _u,int _v,int _next){ 18 u=_u;v=_v;next=_next; 19 } 20 }edge[N*N]; 21 int head[N],cnt; 22 int dfn[N],low[N],stack[N],id[N],num,dep,top; 23 bool instack[N]; 24 vector
            
             V[N]; 25 int c[N],deg[N]; 26 void init(){ 27 memset(head,-1,sizeof(head)); 28 cnt=0; 29 } 30 void add(int u,int v){ 31 edge[cnt]=Edge(u,v,head[u]);head[u]=cnt++; 32 } 33 void tarjan(int u){ 34 int v; 35 dfn[u]=low[u]=++dep; 36 stack[++top]=u; 37 instack[u]=1; 38 for(int k=head[u];k!=-1;k=edge[k].next){ 39 v=edge[k].v; 40 if(!dfn[v]){ 41 tarjan(v); 42 low[u]=min(low[u],low[v]); 43 }else if(instack[v]){ 44 low[u]=min(low[u],dfn[v]); 45 } 46 } 47 if(dfn[u]==low[u]){ 48 ++num; 49 do{ 50 v=stack[top--]; 51 instack[v]=0; 52 id[v]=num; 53 }while(u!=v); 54 deg[num]=0; 55 V[num].clear(); 56 } 57 } 58 int n; 59 int x[N]; 60 int opp(int x){ 61 return x
             

Q; 78 for(int i=0;i<2*n;i++) 79 for(int k=head[i];k!=-1;k=edge[k].next){ 80 int v=edge[k].v; 81 if(id[i]!=id[v]){ 82 V[id[v]].push_back(id[i]); 83 deg[id[i]]++; 84 } 85 } 86 memset(c,0,sizeof(c)); 87 for(int i=1;i<=num;i++) 88 if(deg[i]==0)Q.push(i); 89 while(!Q.empty()){ 90 int p=Q.front();Q.pop(); 91 if(c[p]==0){ 92 c[p]=1; 93 c[x[p]]=-1; 94 } 95 for(int i=0;i