luogu 2-SAT 问题

题目大意：给出n个bool变量，以及m个条件，条件为x,vx,y,vy，表示 x == vx || y == vy 。

求匹配。

题解：

最近新学了一下2-SAT算法。2-SAT指有若干个bool变量（显然有1/0两个值），还给出若干限定条件，比如:

t1 || t2

t1 || !t2

t1 && t2

t1 && -t2

等等。

然后要求找匹配方案。

首先大家应该听过差分约束，差分约束是用最短路处理数的大小关系等问题。

而2-SAT就高级多了，他是将关系映射到图上，然后用tarjan等方法判断情况是否存在。

具体操作是：

若t1成立则t2一定成立，就从t1向t2连一条边。

比如本题（t1成立或t2成立）：

! t1 -> t2

! t2 -> t1

然后看看$i$和$i+n( !i )$是否在一个集里，在的话就不合法。

最后跑tarjan缩点，按拓扑逆序处理状态。由于tarjan是正向跑的，那就在$bel [ i ]<bel[ n + i ]$时输出1，要么输出0。

代码：

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define N 1000050

int n,m,hed[*N],cnt;

struct EG

{

    int to,nxt;

}e[*N];

void ae(int f,int t)

{

    e[++cnt].to = t;

    e[cnt].nxt = hed[f];

    hed[f] = cnt;

}

int dep[*N],low[*N],tim;

int s[*N],tl;

bool vis[*N];

int bel[*N],bc;

void tarjan(int u)

{

    dep[u]=low[u]=++tim;

    s[++tl]=u;

    vis[u]=;

    for(int j=hed[u];j;j=e[j].nxt)

    {

        int to = e[j].to;

        if(!dep[to])

        {

            tarjan(to);

            low[u]=min(low[u],low[to]);

        }else if(vis[to])

        {

            low[u]=min(low[u],dep[to]);

        }

    }

    if(dep[u]==low[u])

    {

        bc++;

        int c=-;

        while(c!=u)

        {

            c=s[tl--];

            vis[c]=;

            bel[c]=bc;

        }

    }

}

int main()

{

    scanf("%d%d",&n,&m);

    int x,vx,y,vy;

    for(int i=;i<=m;i++)

    {

        scanf("%d%d%d%d",&x,&vx,&y,&vy);

        ae(x+vx*n,y+(!vy)*n);

        ae(y+vy*n,x+(!vx)*n);

    }

    for(int i=;i<=*n;i++)

        if(!dep[i])

            tarjan(i);

    for(int i=;i<=n;i++)

    {

        if(bel[i]==bel[i+n])

        {

            printf("IMPOSSIBLE\n");

            return ;

        }

    }

    printf("POSSIBLE\n");

    for(int i=;i<=n;i++)

    {

        printf("%d ",bel[i]<bel[i+n]);

    }

    printf("\n");

    return ;

}

巴特西

luogu 2-SAT 问题

最新文章

热门文章