2-SAT的ZZ学习

这个网上写的这个\(2-sat\)有点难看啊??

还是我太菜了??看理论性的东西根本就看不进去

害,还是我自己给我自己写一篇吧!!

啥是2-sat

就是满足二元关系的解,

所谓二元关系就是给你一堆类似'我是你爹你就必须是摇摆兵的爹'这样的东西

咋解??

这个我们就可以沿着这个关系,不断地向前推进

只要自己的两种选择不会互相推出来,那就是合法解喽

比如说,我是你爹你必须是摇摆兵的爹,你是摇摆兵爹我就必须是你儿子,我是你儿子你就必须是我儿子

这个东西就无解了,因为我是你爹你就必须是我爹。。。。

实现??

发现这就是一个环,也就是一个有向图的强连通分量,于是我们就缩点就好了

如果每个点的两种选择不在同一个分量里,那就是有解,否则无解。。

那么我们有时候需要找到一组可行解,我们只需要选取拓扑序较大的那个选择就好了

因为拓扑序代表着在二元关系递推的先后,选后面的自然是正确解

而\(tarjan\)的缩点则是拓扑序的反序,于是我们就选分量标号小的那个就好了

实现的时候我比较喜欢把\(true\)放在后面,这样写着比较方便

Luogu4782 2-SAT问题

code
#include<bits/stdc++.h>
using namespace std;
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
int read(){
    int s=0,t=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')t=-1;ch=getchar();}
    while(isdigit(ch)){s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
    return s*t;
}
const int N=2e6+5;
int n,m;
struct E{int to,nxt;}e[N*2];
int head[N],rp;
void add_edg(int x,int y){
    // cout<<x<<" "<<y<<endl;
    e[++rp].to=y;e[rp].nxt=head[x];head[x]=rp;
}
int dfn[N],low[N],cnt;
int bl[N],cbl,sta[N],top;
void tarjan(int x){
    dfn[x]=low[x]=++cnt;
    sta[++top]=x;
    for(int i=head[x];i;i=e[i].nxt){
        int y=e[i].to;
        if(!dfn[y])tarjan(y),low[x]=min(low[x],low[y]);
        else if(!bl[y])low[x]=min(low[x],dfn[y]);
    }
    if(dfn[x]==low[x]){
        bl[x]=++cbl;
        while(sta[top]!=x)bl[sta[top]]=cbl,top--;
        top--;
    }
}
signed main(){
    n=read();m=read();
    fo(i,1,m){
        int x=read(),a=read(),y=read(),b=read();
        add_edg((a^1)*n+x,b*n+y);
        add_edg((b^1)*n+y,a*n+x);
    }
    fo(i,1,2*n)if(!dfn[i])tarjan(i);
    fo(i,1,n)if(bl[i]==bl[i+n]){printf("IMPOSSIBLE");return 0;}
    printf("POSSIBLE\n");
    fo(i,1,n)if(bl[i]<bl[i+n])printf("0 ");else printf("1 ");
}

如果要找字典序最小的解,那就直接爆搜就好了

上一篇:[学习笔记]2-SAT


下一篇:2-SAT学习笔记