Loading...

洛谷P4782【模板】2-SAT 问题

check评论:0 条 remove_red_eye浏览量:408 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-10-15

这道题是$2-sat$问题的模板题

先来说一下什么是$2-sat$问题:

如果我们对于$n$件事情,需要满足$m$个条件,比如$i$成立$j$就不能成立,$i$成立$j$就必须成立这一类,我们就将$n$件事情描述为$2n$个点,$1 - n$分别表示的是当前事件的真状态,$n+1-2n$就代表其假状态,我们就分别对其连边,然后进行$tarjan$缩点,如果$i$和$i+n$在同一个强连通分量就捕星了

这个算法的时间复杂度瓶颈就是$tarjan$,时间复杂度$(n+m)$

#include <bits/stdc++.h>
using namespace std;
int dfn[2000010],low[2000010],belong[2000010],na;
int head[2000010],n,m,cnt;
struct edge
{
    int next,to;
}e[4000040];
void add(int u,int v)
{
    cnt++;
    e[cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
stack<int> st;
void tarjan(int u)
{
    dfn[u]=low[u]=++cnt;
    st.push(u);
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(!belong[v])
        {
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(low[u]==dfn[u])
    {
        na++;
        while(1)
        {
            int v=st.top();
            st.pop();
            belong[v]=na;
            if(v==u)
            {
                break;
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        int e=b^1;
        int f=d^1;
        add(a+e*n,c+d*n);
        add(c+f*n,a+b*n);
    }
    cnt=0;
    for(int i=1;i<=(n<<1);i++)
    {
        if(!dfn[i])
        {
            tarjan(i);
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(belong[i]==belong[i+n])
        {
            cout<<"IMPOSSIBLE";
            return 0;
        }
    }
    cout<<"POSSIBLE\n";
    for(int i=1;i<=n;i++)
    {
        printf("%d ",belong[i]>belong[i+n]);
    }
}

chevron_left $splay$ 学习笔记
洛谷P1541 乌龟棋 chevron_right

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名