题解 P4782 【【模板】2-SAT 问题】

Xie_BR · 2019-08-13 20:35:46 · 题解

我不会告诉你我在这道题上死了多少次。。。

废话不多说，这道题是一个2-SAT的模板题（不知道2-SAT是什么的小伙伴可以去网上找找，Xie_BR在此不做过多的解释）

首先

对于2-SAT来说，Xie_BR建议使用

Tarjan + Topsort

这是很好很好的方法，简单明了，只有200行

先建边，通过逻辑推理，发现1或0的关系原来可以这么建边：

int x,a,y,b;
scanf("%d%d%d%d",&x,&a,&y,&b);
if(a)
{
    if(b)
    {
        add(x+n,y);
        add(y+n,x);
    }else
    {
        add(y,x);
        add(x+n,y+n);
    }
}else
{
    if(b)
    {
        add(x,y);
        add(y+n,x+n);
    }else
    {
        add(x,y+n);
        add(y,x+n);
    }
}

然后我们需要通过tarjan+缩点合并环，最后计数。

在此十分感谢spj！！！

最后，我们来看看

AC代码：

#include<bits/stdc++.h>
#define MK 5000010
using namespace std;
int n,m;

struct edge
{
    int to,next,f;
}e[MK*2];

int h[MK],ei = 0;

void add(int x,int y)
{
    ei++;
    e[ei].to = y;
    e[ei].f = x;
    e[ei].next = h[x];
    h[x] = ei;
}

stack<int>st;
int dfn[MK],cnt[MK],stindex = 0,tmindex = 0,indegree[MK];
int low[MK],team[MK],col[MK];

void tarjan(int f)
{
    stindex++;
    low[f] = dfn[f] = stindex;
    st.push(f);
    for(int i=h[f];i;i=e[i].next)
    {
        int to = e[i].to;
        if(dfn[to]==0)
        {
            tarjan(to);
            low[f] = min(low[f],low[to]);
        }else
        {
            if(team[to]==0)
            {
                low[f] = min(low[f],dfn[to]);
            }
        }
    }
    if(low[f] == dfn[f])
    {
        tmindex++;
        while(1)
        {
            int top = st.top();
            st.pop();
            team[top] = tmindex;
            cnt[tmindex]++;
            if(top==f)
            {
                break;
            }
        }
    }
    return; 
}

int opt[MK];

int check()
{
    for(int i=1;i<=n;i++)
    {
        if(team[i]==team[i+n])
        {
            return 0;
        }
        opt[team[i]] = team[i+n];
        opt[team[i+n]] = team[i];
    }
    return 1;
}

void suodian()
{
    memset(h,0,sizeof(h));
    int newei = ei;
    ei = 0;
    for(register int i=1;i<=newei;i++)
    {
        int f = e[i].f;
        int to = e[i].to;
        if(team[f]==team[to])
        {
            continue;
        }
        indegree[team[f]]++;
        add(team[to],team[f]);
    }
    return;
}

void topsort()
{
    queue<int>qu;
    for(int i=1;i<=tmindex;i++)
    {
        if(indegree[i]==0)
        {
            qu.push(i);
        }
    }
    while(!qu.empty())
    {
        int f1 = qu.front();
        qu.pop();
        if(col[f1]==0)
        {
            col[f1] = 1;
            col[opt[f1]] = 2;
        }
        for(int i=h[f1];i;i=e[i].next)
        {
            int to = e[i].to;
            indegree[to]--;
            if(indegree[to]==0)
            {
                qu.push(to);
            }
        }
    }
    return;
}

void out()
{
    printf("POSSIBLE\n");
    for(int i=1;i<=n;i++)
    {
        if(col[team[i]]==1)
        {
            printf("1 ");
        }else
        {
            printf("0 ");
        }
    }
    return;
}

void dotarjan()
{
    for(int i=1;i<=2*n;i++)
    {
        if(!dfn[i])
        {
            tarjan(i);
        }
    }
    return;
}

signed main()
{
    scanf("%d%d",&n,&m);
    while(m--)
    {
        int x,a,y,b;
        scanf("%d%d%d%d",&x,&a,&y,&b);
        if(a)
        {
            if(b)
            {
                add(x+n,y);
                add(y+n,x);
            }else
            {
                add(y,x);
                add(x+n,y+n);
            }
        }else
        {
            if(b)
            {
                add(x,y);
                add(y+n,x+n);
            }else
            {
                add(x,y+n);
                add(y,x+n);
            }
        }
    }
    dotarjan();
    if(!check())
    {
        printf("IMPOSSIBLE\n");
        return 0;
    }
    suodian();
    topsort();
    out();
    return 0;
} 

不多不多，也就200行。
蒟蒻的想法可能和幼稚，大佬指教啊啊啊啊啊啊啊啊啊！！！