POJ3678KatuPuzzle(2

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了POJ3678KatuPuzzle(2，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2475字，纯文字阅读大概需要4分钟。

内容图文

POJ 3678 Katu Puzzle(2-SAT) http://poj.org/problem?id=3678 题意: 一个N个顶点和M条边的有向图,每个顶点能取0或1两个.现在每条边被一个操作符(or,and,xor)以及一个(0或1)标记了,表示a与b按操作符运算的结果是(0或1).问你该有向图是否有可行解? 分析: 由于

POJ 3678 Katu Puzzle(2-SAT)

http://poj.org/problem?id=3678

题意:

一个N个顶点和M条边的有向图,每个顶点能取0或1两个值.现在每条边被一个操作符(or,and,xor)以及一个值(0或1)标记了,表示a与b按操作符运算的结果是值(0或1).问你该有向图是否有可行解?

分析:

由于每个点只能取0或1两个值,所以我们把该问题转化为2-SAT问题.原图中的每个点对应2-SAT中的每个点.对于每种运算有下列转换方式:

a and b = 0 转换为 a=0 或 b=0

a and b = 1 转换为 a=1 且 b=1 即添加边 2*a->2*a+1 2*b->2*b+1(只要a为0或b为0必然引起矛盾)

a or b = 0 转换为 2*a+1->2*a 2*b+1->2*b(只要a为1或b为1必然引起矛盾)

a or b = 1 转换为 a=1 或b=1

a xorb=0转换为 a=1且b=1 或 a=0且b=0 即连下面的边:

2*a->2*b 2*b->2*a 2*a+1->2*b+1 2*b+1->2*a+1.

a xor b=1 转换为a=1且b=0 或a=0且b=1 则连下面的边:

2*a+1->2*b 2*b->2*a+1 2*a->2*b+1 2*b+1->2*a

AC代码:

#include
#include
#include
#include
using namespace std;
const int maxn=1000+10;
struct TwoSAT
{
    int n;
    vector G[maxn*2];
    int S[maxn*2],c;
    bool mark[maxn*2];

    bool dfs(int x)
    {
        if(mark[x^1]) return false;
        if(mark[x]) return true;
        mark[x]=true;
        S[c++]=x;
        for(int i=0;i<G[x].size();i++)
            if(!dfs(G[x][i])) return false;
        return true;
    }

    void init(int n)
    {
        this->n=n;
        for(int i=0;i<n*2;i++) G[i].clear();
        memset(mark,0,sizeof(mark));
    }

    void add_clause(int x,int xval,int y,int yval)//这里的函数做了修改,只加单向边
    {
        x=x*2+xval;
        y=y*2+yval;
        G[x].push_back(y);
    }

    bool solve()
    {
        for(int i=0;i<2*n;i+=2)
        if(!mark[i] && !mark[i+1])
        {
            c=0;
            if(!dfs(i))
            {
                while(c>0) mark[S[--c]]=false;
                if(!dfs(i+1)) return false;
            }
        }
        return true;
    }
}TS;
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    TS.init(n);
    int a,b,c;
    char op[10];
    for(int i=0;i<m;i++)
    {
        scanf("%d%d%d%s",&a,&b,&c,op);
        if(op[0]=='A')
        {
            if(c==0)
            {
                TS.add_clause(a,1,b,0);
                TS.add_clause(b,1,a,0);
            }
            else if(c==1)
            {
                TS.add_clause(a,0,a,1);
                TS.add_clause(b,0,b,1);
            }
        }
        else if(op[0]=='O')
        {
            if(c==0)
            {
                TS.add_clause(a,1,a,0);
                TS.add_clause(b,1,b,0);
            }
            else if(c==1)
            {
                TS.add_clause(a,0,b,1);
                TS.add_clause(b,0,a,1);
            }
        }
        else if(op[0]=='X')
        {
            if(c==0)
            {
                TS.add_clause(a,0,b,0);
                TS.add_clause(a,1,b,1);
                TS.add_clause(b,0,a,0);
                TS.add_clause(b,1,a,1);
            }
            else if(c==1)
            {
                TS.add_clause(a,0,b,1);
                TS.add_clause(a,1,b,0);
                TS.add_clause(b,0,a,1);
                TS.add_clause(b,1,a,0);
            }
        }
    }
    if(TS.solve()) printf("YES\n");
    else printf("NO\n");
    return 0;
}

内容总结

以上是互联网集市为您收集整理的POJ3678KatuPuzzle(2全部内容，希望文章能够帮你解决POJ3678KatuPuzzle(2所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端