zcmimi's blog
avatar
zcmimi
2020-10-02 23:34:21

SAT指Satisfiability(可满足性问题)

k-SAT指每个限制有k个条件,而当k>2时该问题为NP完全的,只能暴力

LG 4782 【模板】2-SAT 问题

n个布尔变量x_1,x_2,\dots,x_n,另有m个需要满足的条件,每个条件的形式都是「x_itrue/falsex_jtrue/false」.

比如「x_1truex_3false」、「x_7falsex_2false」。

2-SAT问题的目标是给每个变量赋值使得所有条件得到满足。

以下把truefalse理解为选或不选

对于每个变量x建立x,\neg x,表示选或不选

对于每个限制,连边方式如下:

条件 连边
xy必须同时选 x\to y,\neg x\to \neg y
xy不能同时选(本题条件) x\to \neg y, y\to \neg x
xy任选一个 \neg x\to y,\neg y \to x

x\to y的含义可以理解为选x则必须选y,

x\to \neg y的含义可以理解为选x则不能选y,

\neg x\to y的含义可以理解为不选x则必须选y,

\neg x\to \neg y的含义可以理解为不选x则不选y

建图后用tarjan求出强连通分量

可以发现在同一强连通分量中的点要么都选,要么都不选

如果存在x\neg x在同一强连通分量中,那么无解

那么如何构造出解呢?

tarjan之后我们得到了一张拓扑图,且图中如果x可以到达y,则选择x时必须选择y

我们只要对每个变量x,选择x\neg x中拓扑序较小的即可(更先出栈,影响其他点更少)

#include<bits/stdc++.h>
const int N=2000011;
int n,m,cnt,head[N];
struct edge{int to,nxt;}e[N*2];
void add(int x,int y){e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;}
int dfn[N],low[N],sz,st[N],tp,bl[N],tt;
bool v[N];
void cmin(int&x,int y){if(y<x)x=y;}
void tarjan(int x){
    dfn[x]=low[x]=++sz;st[++tp]=x;v[x]=1;
    for(int i=head[x],to;to=e[i].to,i;i=e[i].nxt)
        if(!dfn[to])tarjan(to),cmin(low[x],low[to]);
        else if(v[to])cmin(low[x],dfn[to]);
    if(low[x]==dfn[x]){
        ++tt;
        while(int k=st[tp--]){
            bl[k]=tt;v[k]=0;
            if(k==x)break;
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    int x,y,vx,vy;
    for(int i=1;i<=m;++i)
        scanf("%d%d%d%d",&x,&vx,&y,&vy),
        add(x+n*(vx^1),y+n*(vy&1)), // ¬x -> y
        add(y+n*(vy^1),x+n*(vx&1)); // ¬y -> x
    for(int i=1;i<=n*2;++i)if(!dfn[i])tarjan(i);
    for(int i=1;i<=n;++i)
        if(bl[i]==bl[i+n])return puts("IMPOSSIBLE"),0;
    puts("POSSIBLE");
    for(int i=1;i<=n;++i)
        putchar(bl[i]>bl[i+n]?'1':'0'),putchar(' ');
}

练习

LG 4171 [JSOI2010]满汉全席

LG 5782 [POI2001]和平委员会

LG 6378 [PA2010]Riddle

LG 3825 [NOI2017]游戏

2-SAT
comment评论
Search
search