2-sat学习笔记

2-sat

题目：[模板]2-SAT 问题

题目描述:

有n个布尔变量，另有m个需要满足的条件，每个条件的形式都是“为true/false或为true/false”。比如“为真或为假”、“为假或为假”。2-SAT 问题的目标是给每个变量赋值使得所有条件得到满足。

题解：

0表示不选，1表示选

1.a=0 , a->a'

2.a=1 , a'->a

3.a=1那么b=1 , a->b b'->a'(隐藏b=0那么a=0)

4.a=0那么b=0 , a'->b' b->a(隐藏b=1那么a=1)

5.a=1那么b=0 , a->b' b->a'(隐藏b=1那么a=0)

6.a=0那么b=1 , a'->b b'->a(隐藏b=0那么a=1)

7.a=0并且b=0 a=0并且b=1 a=1并且b=0 a=1并且b=1 参考3-6,进行合并

8.a^b=0 a^b!=0 参考3-6,进行合并

如果col[a]==col[a'],那么无解。

关于求一组解，由于我们知道tarjan的dfn序其实就是拓扑的反序，所以当col[a]<col[a']时，a=1。

代码：

#include<bits/stdc++.h>
using namespace std;
#define next Next
#define last Last
/*char buf[1<<21],*p1=buf,*p2=buf;
inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}*/
#define gc getchar
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
const int N=2e6+5;
int n,m,top,deep,tot,color;
int dfn[N],low[N],zhan[N],col[N],head[N];
bool vis[N];
struct node{
    int too,next;
}edge[N];
void add(int a,int b)
{
    edge[++top].too=b;edge[top].next=head[a];head[a]=top;
}
void tarjan(int u)
{
    deep++;dfn[u]=low[u]=deep;
    vis[u]=true;zhan[++tot]=u;
    for(int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].too;
        if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}
        else if(vis[v])low[u]=min(low[u],low[v]);
    }
    if(dfn[u]==low[u])
    {
        color++;vis[u]=false;col[u]=color;
        while(zhan[tot]!=u)
        {
            vis[zhan[tot]]=false;
            col[zhan[tot]]=color;
            tot--;
        }
        tot--;
    }
}
bool TWO_SAT()
{
    for(int i=1;i<=2*n;i++)
        if(!dfn[i])tarjan(i);
    for(int i=1;i<=n;i++)
        if(col[i]==col[i+n])return false;
    return true;
}
signed main()
{
    n=read();m=read();
    for(int i=1;i<=m;i++)
    {
        int a=read(),x=read(),b=read(),y=read();
        if(x==0)
        {
            if(y==0)//a=1那么b=0(b=1那么a=0) 
            {
                add(a,b+n);
                add(b,a+n);
            }
            else{//a=1那么b=1(b=0那么a=0) 
                add(a,b);
                add(b+n,a+n);
            }
        }
        else{
            if(y==0)//a=0那么b=0(b=1那么a=1) 
            {
                add(a+n,b+n);
                add(b,a);
            }
            else{//a=0那么b=1(b=0那么a=1) 
                add(a+n,b);
                add(b+n,a);
            }
        }
    }
    if(TWO_SAT())
    {
        puts("POSSIBLE");
        for(int i=1;i<=n;i++)
            printf("%d ",col[i]<col[i+n]);
    }
    else printf("IMPOSSIBLE");
    return 0;
}

题目：[JSOI2010]满汉全席

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int T,n,m,x,y,xx,yy,deep,color,cnt,tot,top;
int dfn[N],low[N],head[N],col[N],zhan[N];
char s1[50],s2[50];
struct node{
    int too,next;
}edge[N];
bool vis[N];
void add(int a,int b)
{
    edge[++top].too=b;edge[top].next=head[a];head[a]=top;
}
void tarjan(int u)
{
    deep++;
    dfn[u]=low[u]=deep;
    zhan[++tot]=u;vis[u]=true;
    for(int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].too;
        if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}
        else if(vis[v])low[u]=min(low[u],low[v]);
    }
    if(dfn[u]==low[u])
    {
        color++;col[u]=color;vis[u]=false;
        while(zhan[tot]!=u)
        {
            col[zhan[tot]]=color;
            vis[zhan[tot]]=false;
            tot--;
        }
        tot--;
    }
}
bool TWO_SAT()
{
    for(int i=1;i<=2*n;i++)
        if(!dfn[i])tarjan(i);
    for(int i=1;i<=n;i++)
        if(col[i]==col[i+n])return false;
    return true;
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        cnt=tot=0;
        for(int i=1;i<=2*n;i++)
            head[i]=low[i]=dfn[i]=col[i]=vis[i]=0;
        for(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);
            }
        }
        if(TWO_SAT())printf("GOOD\n");
        else printf("BAD\n");
    }
}

题目：[NOI2017]游戏

题解：

a,b,c三种赛道都是普通2-set。但x赛道不是。

怎么办？由于x赛道数量少，我们暴力枚举是变成a或b即可。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m,num,deep,color,tot,top;
int dfn[N],low[N],head[N],col[N],zhan[N],b[N],pos[N];
char s[N];
struct node{
    int too,next;
}edge[N];
struct node2{
    int x,a,y,b;
}a[N];
bool vis[N];
/*char buf[1<<21],*p1=buf,*p2=buf;
inline int gc()
{
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
}*/
#define gc getchar
inline int read()
{
    int ret=0,f=0;
    char c=gc();
    while(!isdigit(c))
    {
        if(c=='-')f=1;
        c=gc();
    }
    while(isdigit(c))
    {
        ret=ret*10+c-48;
        c=gc();
    }
    if(f)return -ret;
    return ret;
}
int get(int x,int c)
{
    if(b[x]==1)return c==2?x:x+n;
    if(b[x]==2||b[x]==3)return c==1?x:x+n;
}
int nxt(int x)
{
    return x>n?x-n:x+n;
}
void clean()
{
    top=color=deep=tot=0;
    memset(head,0,sizeof(head));
    memset(low,0,sizeof(low));
    memset(dfn,0,sizeof(dfn));
    memset(vis,0,sizeof(vis));
    memset(col,0,sizeof(col));
}
void add(int a,int b)
{
    edge[++top].too=b;edge[top].next=head[a];head[a]=top;
}
void build()
{
    for(int i=1;i<=m;i++)
    {
        int x=a[i].x,y=a[i].y;
        if(b[x]==a[i].a)continue;
        int u=get(x,a[i].a),v=get(y,a[i].b);
        if(b[y]==a[i].b)
        {
            add(u,nxt(u));
            continue;
        }
        add(u,v);//选a，一定要选b
        add(nxt(v),nxt(u));//不选b，一定不选a 
    }
}
void tarjan(int u)
{
    deep++;
    dfn[u]=low[u]=deep;
    zhan[++tot]=u;vis[u]=true;
    for(int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].too;
        if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}
        else if(vis[v])low[u]=min(low[u],low[v]);
    }
    if(dfn[u]==low[u])
    {
        color++;col[u]=color;vis[u]=false;
        while(zhan[tot]!=u)
        {
            col[zhan[tot]]=color;
            vis[zhan[tot]]=false;
            tot--;
        }
        tot--;
    }
}
bool TWO_SAT()
{
    for(int i=1;i<=2*n;i++)
        if(!dfn[i])tarjan(i);
    for(int i=1;i<=n;i++)
        if(col[i]==col[i+n])return false;
    return true;
}
void dfs(int x)
{
    if(x>num)
    {
        clean();
        build();
        if(TWO_SAT())
        {
            for(int i=1;i<=n;i++)
            {
                if(col[i]<col[nxt(i)])putchar(b[i]==1?'B':'A');
                else putchar(b[i]==3?'B':'C');
            }
                exit(0);
        }
        return;
    }
    b[pos[x]]=1;
    dfs(x+1);
    b[pos[x]]=2;
    dfs(x+1);
}
int main()
{
    n=read();read();
    cin>>s+1;
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='x')pos[++num]=i;
        b[i]=s[i]-'a'+1;
    }
    m=read();
    char c1,c2;
    for(int i=1;i<=m;i++)
    {
        cin>>a[i].x>>c1>>a[i].y>>c2;
        a[i].a=c1-'A'+1;
        a[i].b=c2-'A'+1;
    }
    dfs(1);
    puts("-1");
    return 0;
}

题目：National Property

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m,deep,color,tot,top,a[N],b[N];
int dfn[N],low[N],head[N],col[N],zhan[N];
struct node{
    int too,next;
}edge[N];
bool vis[N];
void add(int a,int b)
{
    edge[++top].too=b;edge[top].next=head[a];head[a]=top;
}
void tarjan(int u)
{
    deep++;
    dfn[u]=low[u]=deep;
    zhan[++tot]=u;vis[u]=true;
    for(int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].too;
        if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}
        else if(vis[v])low[u]=min(low[u],low[v]);
    }
    if(dfn[u]==low[u])
    {
        color++;col[u]=color;vis[u]=false;
        while(zhan[tot]!=u)
        {
            col[zhan[tot]]=color;
            vis[zhan[tot]]=false;
            tot--;
        }
        tot--;
    }
}
bool TWO_SAT()
{
    for(int i=1;i<=2*n;i++)
        if(!dfn[i])tarjan(i);
    for(int i=1;i<=n;i++)
        if(col[i]==col[i+n])return false;
    return true;
}
int main()
{
    scanf("%d%d",&m,&n);
    for(int j=1;j<=m;j++)
    {
        scanf("%d",&a[0]);
        for(int i=1;i<=a[0];i++)scanf("%d",&a[i]);
        if(j>1)
        {
            for(int i=1;i<=min(a[0],b[0]);i++)
            {
                if(b[i]<a[i])
                {
                    add(a[i],b[i]);
                    add(b[i]+n,a[i]+n);
                    break;
                }
                else if(a[i]<b[i])
                {
                    add(b[i]+n,b[i]);
                    add(a[i],a[i]+n);
                    break;
                }
                if(i==min(a[0],b[0])&&b[0]>a[0])
                {
                    puts("No");
                    return 0;
                }
            }
        }
        for(int i=0;i<=a[0];i++)b[i]=a[i];
    }
    if(TWO_SAT())
    {
        puts("Yes");
        int ans=0;
        for(int i=1;i<=n;i++)
            if(col[i]<col[i+n])ans++;
        cout<<ans<<endl;
        for(int i=1;i<=n;i++)
            if(col[i]<col[i+n])printf("%d ",i);
    }
    else printf("No");
    return 0;
}
xuxuxuxuxu 文章被收录于专栏

信息学竞赛

全部评论
米奇太强了！！米奇天下第一！！！
点赞 回复 分享
发布于 2019-07-19 18:40

相关推荐

11-25 00:45
安徽理工大学 Java
点赞 评论 收藏
分享
头像
11-26 16:16
山东大学 嵌入式软件工程师
提前预习，Leader的PUA话术
实习er：“你表现得很好，部门领导给你打分都很高，转正希望很大”“过两天新来几个实习生，他们简历很优秀，在XX大厂实习过”“这个项目单独给你做，挤一挤时间完成他，其他实习生我没给，对转正有用”“就你这工作态度，以后哪个公司敢要你？”“这么简单的任务都完成不好，你还想不想转正了？”“你别觉得自己了不起，你离我的要求还差得远呢。”“别人怎么都能做好，就你不行？你是不是能力有问题？”“你要是再这样下去，实习评价肯定好不了。”“我对你很失望，你根本没有发挥出你的潜力。”“你怎么这么笨啊？教了你多少次了还不会，我都怀疑你是不是根本没用心。”“你看看你做的这点事儿，就这水平还大学生呢？我随便找个高中生都比...
牛肉爆大虾：我对你是比较失望的，我当初给你的评级是高于你的面试表现的.......（省略200字）
你觉得哪一届的校招最难？ 上班苦还是上学苦呢？
点赞 评论 收藏
分享
11-01 19:18
蚌埠坦克学院 智能驾驶系统工程师
不是哥们
这面试时间是认真的吗😰
Natrium_：这时间我以为飞机票
点赞 评论 收藏
分享
11-27 15:27
北京交通大学 商家运营
运营“偷感很重”
啊啊啊我现在……&nbsp;一边在工位上明目张胆地刷小红书……&nbsp;一边轻轻地奔溃了……&nbsp;为什么，我的工作看起来这么像摸鱼啊！！&nbsp;作为运营我的工作内容之一是发小红书，&nbsp;而发小红书要有网感，&nbsp;于是为了培养网感，&nbsp;我开始沉默地在工位上划起了小红书。。&nbsp;为了表现我正在努力加速成长，&nbsp;我拿出了3台设备，平板、电脑和手机，&nbsp;开始沉默且眼花缭乱地三管齐下划小红书。。&nbsp;但是突然我觉得很不对劲，&nbsp;好像我越努力，&nbsp;看起来就越猖狂。。。&nbsp;救，到底要怎样才能让我看起来偷感不那么重啊！！！&nbsp;我真在上班！&nbsp;我真在上班。吗？
投递小红书等公司10个岗位 >
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

正在热议
# 拼多多求职进展汇总 #
233353次浏览 2031人参与
# 在职场上，你最讨厌什么样的同事 #
5714次浏览 81人参与
# 阿里云管培生offer #
58990次浏览 1748人参与
# 25届秋招总结 #
396617次浏览 3976人参与
# 哪些公司校招卡第一学历 #
32836次浏览 105人参与
# 地方国企笔面经互助 #
6546次浏览 16人参与
# 北方华创开奖 #
66011次浏览 549人参与
# ai智能作图 #
21391次浏览 262人参与
# 硬件兄弟们 甩出你的华为奖状 #
77946次浏览 625人参与
# 实习，投递多份简历没人回复怎么办 #
2435892次浏览 34703人参与
# 工作中，你有没有遇到非常爱骂人的领导？ #
4726次浏览 47人参与
# 实习与准备秋招该如何平衡 #
722808次浏览 8551人参与
# 我的实习求职记录 #
6121642次浏览 83953人参与
# 如果再来一次，你还会选择这个工作吗？ #
110472次浏览 1109人参与
# 25届机械人为了秋招做了哪些准备？ #
24992次浏览 355人参与
# 签了三方后想毁约怎么办 #
18563次浏览 111人参与
# 如果你有一天可以担任公司的CEO，你会做哪三件事？ #
9959次浏览 213人参与
# 机械求职避坑tips #
22158次浏览 240人参与
# 游戏求职进展汇总 #
52769次浏览 344人参与
# 夸夸我的求职搭子 #
132021次浏览 1360人参与
# 腾讯求职进展汇总 #
207574次浏览 1694人参与
# 实习想申请秋招offer，能不能argue薪资 #
35785次浏览 308人参与
牛客网
牛客企业服务