【暖*墟】 #数据结构进阶# 2-SAT问题

求解 2-SAT 问题

使用强连通分量。 对于每个变量 x，建立两个点：x,¬x 分别表示变量 x 取 true 和取 false。

图的节点个数是两倍的变量个数。在存储方式上，可以给第 i 个变量标号为 i，其对应的反值标号为 i+n。

对于每个要求(a∨b)，转换为 （ ¬a→b ）∧（¬b→a ） ，即：「若 a 假则 b 必真，若 b 假则 a 必真」。

然后按照箭头的方向建有向边，进行相关的缩点、拓扑排序操作，达到题目要求。

相关例题分析

1.【洛谷p4782】模板：2-sat问题 

#include<cmath>
#include<cstdio>
#include<cstring>
#include<cassert>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<deque>
using namespace std;
typedef long long ll;

#define R register

/*【p4782】2-sat问题
有n个布尔变量x1​~xn，另有m个需要满足的条件，
每个条件的形式都是“xi为true/false或xj​为true/false”。
2-SAT问题的目标是给每个变量赋值使得所有条件得到满足。*/

void reads(int &x){ //读入优化（正负整数）
    int f=1;x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    x*=f; //正负号
}

const int N=2500019,M=5000019;

int n,m,dfn[N],low[N],stack[N],vis[N];
 
int dfn_=0,top_=0,colnum=0,col[N];//siz[N];

int head[N],tot=0,rd[N],okk=1;

struct node{ int ver,nextt; }e[M];

inline void add(R int x,R int y){ 
    e[++tot].nextt=head[x],e[tot].ver=y,head[x]=tot; 
}

inline void tarjan(int x){
    dfn[x]=low[x]=++dfn_,stack[++top_]=x,vis[x]=1;
    for(R int i=head[x];i;i=e[i].nextt){
        if(!dfn[e[i].ver]) 
　　　　　　tarjan(e[i].ver),low[x]=min(low[x],low[e[i].ver]);
        else if(vis[e[i].ver]) low[x]=min(low[x],dfn[e[i].ver]);
    } if(dfn[x]==low[x]){
        col[x]=++colnum; vis[x]=0; //siz[colnum]++; 
        while(stack[top_]!=x){ //x上方的节点是可以保留的
            col[stack[top_]]=colnum; //siz[colnum]++;
            vis[stack[top_]]=0,top_--;
        } top_--; //col数组记录每个点所在连通块的编号
    }
}

int main(){
    int u,v,uw,vw; reads(n),reads(m);
    for(R int i=1;i<=m;i++){
        reads(u),reads(uw),reads(v),reads(vw);
        int notu=uw^1,notv=vw^1; //命题的否定
        add(u+notu*n,v+vw*n),add(v+notv*n,u+uw*n);//(非u,v),(非v,u)
    } for(R int i=1;i<=n*2;i++) if(!dfn[i]) tarjan(i);
    for(R int i=1;i<=n;i++) if(col[i]==col[i+n]){ okk=0; break; }
    if(okk){ printf("POSSIBLE
"); //↓↓此情况下的真假
        for(int i=1;i<=n;i++) printf("%d ",col[i]>col[i+n]); 
    } else printf("IMPOSSIBLE
"); return 0;
}

2.【洛谷p4171】满汉全席 

#include<cmath>
#include<cstdio>
#include<cstring>
#include<cassert>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<deque>
using namespace std;
typedef long long ll;

#define R register

/*【p4171】满汉全席
n个材料，每个材料可选满式或汉式，m个评委各有喜好。
必须满足每个评委喜欢的两道菜之一，问是否可能。*/

//对于每样材料i拆成两个点，结点i表示满式，结点i+n表示汉式。

/* 每个评委的限制条件都可以看做‘或’的形式：
1.mi,mj：连边i+n到j，表示若i为汉式，则j必须为满式；
　　　　　　连边j+n到i，表示若j为汉式，则i必须为满式
2.mi,hj：连边i+n到j+n，表示若i为汉式，则j必须为汉式；
　　　　　　连边j到i，表示若j为满式，则i必须为满式
3.hi,hj：连边i到j+n，表示若i为满式，则j必须为汉式；
　　　　　　连边j到i+n，表示若j为满式，则i必须为汉式
4.hi,mj：连边i到j，表示若i为满式，则j必须为满式；
　　　　　　连边j+n到i+n，表示若j为汉式，则i必须为汉式 */

//建图后tarjan求强连通分量， 判断i和i+n是否属于同一个强连通分量，即可行性。

void reads(int &x){ //读入优化（正负整数）
    int f=1;x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    x*=f; //正负号
}

const int N=519,M=2519;

int n,m,dfn[N],low[N],stack[N],vis[N];
 
int dfn_=0,top_=0,colnum=0,col[N],siz[N];

int head[N],tot=0,rd[N],okk=0;

struct node{ int ver,nextt; }e[M];

inline void add(R int x,R int y){ 
    e[++tot].nextt=head[x],e[tot].ver=y,head[x]=tot; 
}

inline void tarjan(int x){
    dfn[x]=low[x]=++dfn_,stack[++top_]=x,vis[x]=1;
    for(R int i=head[x];i;i=e[i].nextt){
        if(!dfn[e[i].ver]) 
　　　　　　tarjan(e[i].ver),low[x]=min(low[x],low[e[i].ver]);
        else if(vis[e[i].ver]) low[x]=min(low[x],dfn[e[i].ver]);
    } if(dfn[x]==low[x]){
        col[x]=++colnum; vis[x]=0; //siz[colnum]++; 
        while(stack[top_]!=x){ //x上方的节点是可以保留的
            col[stack[top_]]=colnum; //siz[colnum]++;
            vis[stack[top_]]=0,top_--;
        } top_--; //col数组记录每个点所在连通块的编号
    }
}

void init(){ 
    okk=1,dfn_=top_=colnum=tot=0;
    memset(head,0,sizeof(head));
    memset(col,0,sizeof(col));
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
}

char s1[519],s2[519];

int main(){
    int T; cin>>T;
    while(T--){
        init(); reads(n),reads(m);
        for(R int i=1;i<=m;i++){
            scanf("%s%s",s1,s2);
            int u=0,v=0,k; //字符串转成对应数字
            k=1;while(s1[k]>='0'&&s1[k]<='9')u=u*10+s1[k++]-'0';
            k=1;while(s2[k]>='0'&&s2[k]<='9')v=v*10+s2[k++]-'0';
            if(s1[0]=='m'){ //对于每位评委的限制，选择建边
                if(s2[0]=='h') add(u+n,v+n),add(v,u);
                else if(s2[0]=='m') add(u+n,v),add(v+n,u);
            } else if(s1[0]=='h'){
                if(s2[0]=='h') add(u,v+n),add(v,u+n);
                else if(s2[0]=='m') add(u,v),add(v+n,u+n);
            }
        } for(R int i=1;i<=n*2;i++) if(!dfn[i]) tarjan(i);
        for(R int i=1;i<=n;i++) if(col[i]==col[i+n]){ okk=false; break; }
        if(okk) printf("GOOD
"); else printf("BAD
");
    }
}

3.【poj3207】Panda's Trick

#include<cmath>
#include<cstdio>
#include<cstring>
#include<cassert>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<deque>
using namespace std;
typedef long long ll;

#define R register

/*【poj3207】Panda's Trick
平面上有一个圆，圆的边上按顺时针放着n个点。
现在要连m条边(a,b)，a到b可以从圆的内部或外部连接。
问能不能连接这m条边，使这些边都不相交。*/

/*【分析】设边i连接点A,B，边j连接点C,D
线段i与j在圆内是否相交就是线段AB与线段CD是否相交
可以证明，如果i与j在圆内不能共存，则在圆外也一定不能共存。
即：i内j外，建边i−>j′; i外j内，建边i′−>j;
    j内i外，建边j−>i′; j外i内，建边j′−>i。*/

void reads(int &x){ //读入优化（正负整数）
    int f=1;x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    x*=f; //正负号
}

const int N=5019,M=500019;

int n,m,dfn[N],low[N],stack[N],vis[N];
 
int dfn_=0,top_=0,colnum=0,col[N],u[N],v[N];

int head[N],tot=0,rd[N],okk=0;

struct node{ int ver,nextt; }e[M];

int xj(int a,int b){
    if(u[a]<=u[b]&&u[b]<=v[a]&&v[b]>=v[a]) return true;
    if(u[b]<=u[a]&&u[a]<=v[b]&&v[a]>=v[b]) return true;
}

inline void add(R int x,R int y){ 
    e[++tot].nextt=head[x],e[tot].ver=y,head[x]=tot; 
}

inline void tarjan(int x){
    dfn[x]=low[x]=++dfn_,stack[++top_]=x,vis[x]=1;
    for(R int i=head[x];i;i=e[i].nextt){
        if(!dfn[e[i].ver]) 
            tarjan(e[i].ver),low[x]=min(low[x],low[e[i].ver]);
        else if(vis[e[i].ver]) low[x]=min(low[x],dfn[e[i].ver]);
    } if(dfn[x]==low[x]){
        col[x]=++colnum; vis[x]=0; //siz[colnum]++; 
        while(stack[top_]!=x){ //x上方的节点是可以保留的
            col[stack[top_]]=colnum; //siz[colnum]++;
            vis[stack[top_]]=0,top_--;
        } top_--; //col数组记录每个点所在连通块的编号
    }
}

bool solve(){
    for(int i=1;i<=m;i++) if(!dfn[i]) tarjan(i);
    for(int i=1;i<=m;i++) 
        if(col[i]==col[i+m]) return false;
    return true;
}

int main(){
    reads(n),reads(m);
    for(int i=1;i<=m;i++){
        reads(u[i]),reads(v[i]);
        if(u[i]>v[i]) swap(u[i],v[i]);
    } for(int i=1;i<=m;i++)
        for(int j=i+1;j<=m;j++) if(xj(i,j))
            add(i,j+m),add(j,i+m),add(j+m,i),add(i+m,j);
    if(solve()) printf("panda is telling the truth...
");
    else printf("the evil panda is lying again
");
}