首页 未分类

2-sat

$\quad\quad$sat=Satisfiability ,可满足性。一般称为$k-sat$问题,但是当 $k>2$ 的时候是个NP完全的,所以我们只考虑 $k=2$ 的情况(不要问为什么不研究 $k=1$ )

$\quad\quad$形式化地讲就是给你 $n$ 个二元组$(a_1,b_1),(a_2,b_2)...$,对于每一个二元组你需要满足一些限制。

$\quad\quad$举个例子,放假了,你想约上你的朋友们一起出去玩。但是并不是每个人之间的关系都是这么好。就像你的朋友
$A,B$ 之间有矛盾,不会同时去,又或者 $C,D$ 是很好的朋友,他们要么都不去,要么一起去...那么你现在就需要一种方案使得满足所有的限制,这就是 $2-sat$ 问题


Solve

$\quad\quad$那我们怎么解决这个问题呢?考虑这些限制有什么联系。如果 $(a\lor b)$ 那么当 $a=0$ 时,$b$ 只能为 $1$ ,此时我们就可以把 $¬a$ 向 $b$ 连一条有向边表示前一个满足,后一个必须满足。同时,我们也会 $add(¬b,a)$
$\quad\quad$同理的,对于其他情况我们也可以这么连。并且一般用 $i$ 这个点表示 $a_i$ 取 $0$,$i+n$ 表示$a_i$ 取 $1$。

$\quad\quad$连边的话,如果不想用太多的$if$,那么可以

add(x+(a^1)*n,y+b*n);
add(y+(b^1)*n,x+a*n);

其中 $x,y$ 代表第 $i$ 个元素,$a,b$ 代表限制为$[0,1]$

$\quad\quad$建好图以后,我们跑一个 $Tanjan$ 求强联通分量。显然,如果存在一个 $i$ 使得 $i,i+n$都在同一个强联通分量中,那么肯定是不合法的。

$Q:$如果存在一个点$i$,最终会通向$i+n$,但是他们并不在一个强联通分量里怎么办?
$A:$这样我们会先记录$i+n$,所以最终的决策点也还是$i+n$,并不会选择$i$,不会冲突

$\quad\quad$如果合法的话,可能会存在很多组互不干扰的解,对于的两个点$i,i+n$,显然是谁先被遍历到,那就决定是谁,也就是$dfn$序。至此,$2-sat$的流程就算是讲完了


Problem

【模板】2-SAT 问题

Code

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+9;
inline int read(){
    int f=0,x=0;
    char ch=getchar();
    while(!isdigit(ch)){f|=(ch=='-');ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return f?-x:x;
}
int cnt,n,m;
struct E{
    int pre,to;
}e[2*N];
int last[N];
inline void add(int x,int y){
    e[++cnt].pre=last[x];
    e[cnt].to=y;
    last[x]=cnt;
}
int dfn[N],low[N],idx,sta[N],top,c[N],color;
void Tarjan(int x){
    dfn[x]=low[x]=++idx;
    sta[++top]=x;
    for(int i=last[x];i;i=e[i].pre){
        int to=e[i].to;
        if(!dfn[to]){
            Tarjan(to);
            low[x]=min(low[x],low[to]);
        }else if(!c[to])low[x]=min(low[x],dfn[to]);
    }
    if(low[x]==dfn[x]){
        color++;
        do{
            c[sta[top--]]=color;
        }while(sta[top+1]!=x);
    }return;
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=m;i++){
        int x=read(),a=read(),y=read(),b=read();
        add(x+(a^1)*n,y+b*n);
        add(y+(b^1)*n,x+a*n);
    } 
    for(int i=1;i<=n+n;i++)if(!dfn[i])Tarjan(i);
    for(int i=1;i<=n;i++)
        if(c[i]==c[i+n]){puts("IMPOSSIBLE");return 0;}
    puts("POSSIBLE");
    for(int i=1;i<=n;i++){
        printf("%d ",c[i]>c[i+n]);
    }
    return 0;
}

HNOI2010 平面图判定

$\quad\quad$显然你要把哈密顿回路拉出来形成环,然后再考虑边。显然对于一条边,我们可以选择让他在里面或者翻出去。当然,如果有两条边相交了(指都在里面时相交),那么他们不能同时在里面或外面。这种两两之间的关系很自然就想到$2-sat$去解。

$\quad\quad$但是看到 $m\leq 10000$,会发现我们的关系会是 $m^2$ 级别的,这怎么办呢?利用平面图定理 $e\leq 3*n-6$即可

$\quad\quad$总之当你看到有一些条件,并且是每两个之间的关系时,就要想到$2-sat$




文章评论

目录