问题描述:

给你一张n个节点m条边的图,每一条边包含一个位运算$op$和一个值$c$(0或1)。每条边两个端点权值$op$操作后的结果为$c$。你的任务是求出是否存在这样的图。

输入:

第一行$n (n<=1000), m (m<=100000)$表示n个节点,m条边。
接下来m行每行三个数$a, b, c$以及一个位运算$op$。表示$a, b$之间的一条边。

输出:

直接输出YES或NO。

思路:

不难看出这是一个2-SAT问题。每个点只能取0或1,并且点之间存在一些约束关系。这道题就是2-SAT的一道模版,比较简单。

按照2-SAT的套路,每个点有两种取值,每个值对应一个节点,然后按照约束关系建边(这个比较重要)。由于每个点只能取一个值,所以如果一个点对应的两个取值在同一个环中,则是不可能的。求无向图的环用tarjan就好了。

代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAXN 20005
#define MAXE 2000005
using namespace std;

int n, m, cnt, head[MAXN];
int id, top, tot, low[MAXN], dfn[MAXN], sta[MAXN], bel[MAXN];
bool vis[MAXN];
struct Edge {int to, next;} edge[MAXE];

void addedge(int from, int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}

bool check()
{
    for(int i=1; i<=n; i++) if(bel[i]==bel[i+n]) return false;
    return true;
}

void tarjan(int x)
{
    low[x]=dfn[x]=++id;
    sta[++top]=x; vis[x]=true;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(!dfn[to])
        {
            tarjan(to);
            low[x]=min(low[x], low[to]);
        }
        else if(vis[to]) low[x]=min(low[x], low[to]);
    }
    if(dfn[x]==low[x])
    {
        int y; tot++;
        do
        {
            y=sta[top--]; vis[y]=false;
            bel[y]=tot;
        }while(x!=y);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++)
    {
        int x, y, z; char op[5];
        cin>>x>>y>>z>>op;
        x++; y++;
        if(op[0]=='A' && z==0) addedge(x, y+n), addedge(y, x+n);
        if(op[0]=='A' && z==1) addedge(x+n, x), addedge(y+n, y);
        if(op[0]=='O' && z==0) addedge(x, x+n), addedge(y, y+n);
        if(op[0]=='O' && z==1) addedge(x+n, y), addedge(y+n, x);
        if(op[0]=='X' && z==0) addedge(x, y), addedge(y, x), addedge(x+n, y+n), addedge(y+n, x+n);
        if(op[0]=='X' && z==1) addedge(x, y+n), addedge(x+n, y), addedge(y, x+n), addedge(y+n, x);
    }
    for(int i=1; i<=n*2; i++) if(!dfn[i]) tarjan(i);
    if(check()) printf("YES\n");
    else printf("NO\n");
}

发表评论

邮箱地址不会被公开。 必填项已用*标注