poj 3678 2-SAT问题

时间:2022-09-02 00:18:28

思路:将每个点拆分为两个点 a与a' ,a表示为1,a'表示为0。那么条件给的每个边自然就会存在矛盾,然后根据2-SAT建边就行了。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#define Maxn 3010
#define Maxm 1000000
using namespace std;
int dfn[Maxn],low[Maxn],vi[Maxn],head[Maxn],e,n,m,lab,top,Stack[Maxn],num,id[Maxn];
struct Edge{
int u,v,next,l;
}edge[Maxm];
void init()
{
int i,j;
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
memset(head,-,sizeof(head));
memset(id,,sizeof(id));
memset(vi,,sizeof(vi));
e=lab=num=top=;
}
void add(int u,int v)
{
edge[e].u=u,edge[e].v=v,edge[e].next=head[u],head[u]=e++;
}
void Tarjan(int u)
{
int i,j,v;
dfn[u]=low[u]=++lab;
Stack[top++]=u;
vi[u]=;
for(i=head[u];i!=-;i=edge[i].next)
{
v=edge[i].v;
if(!dfn[v])
{
Tarjan(v);
low[u]=min(low[u],low[v]);
}
if(vi[v])
low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u])
{
++num;
do{
i=Stack[--top];
vi[i]=;
id[i]=num;
}while(i!=u);
}
}
int solve()
{
int i,j;
for(i=;i<=n*;i++)
{
if(!dfn[i])
Tarjan(i);
}
for(i=;i<=n;i++)
{
if(id[i]==id[i+n])
return ;
}
return ;
}
int main()
{
int i,j,a,b,c;
char str[];
while(scanf("%d%d",&n,&m)!=EOF)
{
init();
for(i=;i<=m;i++)
{
scanf("%d%d%d%s",&a,&b,&c,&str);
a++,b++;
if(str[]=='O')
{
if(c==)
{
add(a,b+n);
add(a,b);
add(b,a+n);
add(b,a);
add(a+n,b+n);
add(b+n,a+n);
}
else
{
add(a+n,b);
add(b+n,a);
}
}
if(str[]=='A')
{
if(c==)
{
add(a,b+n);
add(b,a+n);
}
else
{
add(a+n,b);
add(a,b);
add(b+n,a);
add(b,a);
add(a+n,b+n);
add(b+n,a+n);
}
}
if(str[]=='X')
{
if(c==)
{
add(a,b);
add(b+n,a+n);
add(b,a);
add(a+n,b+n);
}
else
{
add(a,b+n);
add(b,a+n);
add(a+n,b);
add(b+n,a);
}
}
}
if(solve())
printf("YES\n");
else
printf("NO\n");
}
return ;
}

poj 3678 2-SAT问题的更多相关文章

  1. HDU 3062 &amp&semi;&amp&semi; HDU 1824 &amp&semi;&amp&semi; POJ 3678 &amp&semi;&amp&semi; BZOJ 1997 2-SAT

    一条边<u,v>表示u选那么v一定被选. #include <iostream> #include <cstring> #include <cstdio&gt ...

  2. POJ 3678 Katu Puzzle(2-SAT,合取范式大集合)

    Katu Puzzle Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 9987   Accepted: 3741 Descr ...

  3. poj 3678 Katu Puzzle&lpar;Two Sat&rpar;

    题目链接:http://poj.org/problem?id=3678 代码: #include<cstdio> #include<cstring> #include<i ...

  4. POJ 3678 Katu Puzzle(2 - SAT) - from lanshui&lowbar;Yang

    Description Katu Puzzle is presented as a directed graph G(V, E) with each edge e(a, b) labeled by a ...

  5. Katu Puzzle POJ - 3678(水2 - sat)

    题意: 有n个未知量,m对未知量之间的关系,判断是否能求出所有的未知量且满足这些关系 解析: 关系建边就好了 #include <iostream> #include <cstdio ...

  6. Katu Puzzle POJ - 3678 (2 - sat)

    有N个变量X1X1~XNXN,每个变量的可能取值为0或1. 给定M个算式,每个算式形如 XaopXb=cXaopXb=c,其中 a,b 是变量编号,c 是数字0或1,op 是 and,or,xor 三 ...

  7. POJ 3678 Katu Puzzle 2-SAT 强连通分量 tarjan

    http://poj.org/problem?id=3678 给m条连接两个点的边,每条边有一个权值0或1,有一个运算方式and.or或xor,要求和这条边相连的两个点经过边上的运算后的结果是边的权值 ...

  8. 基础但是很重要的2-sat POJ 3678

    http://poj.org/problem?id=3678 题目大意:就是给你n个点,m条边,每个点都可以取值为0或者1,边上都会有一个符号op(op=xor or and三种)和一个权值c.然后问 ...

  9. poj 3678 Katu Puzzle&lpar;2-sat&rpar;

    Description Katu Puzzle ≤ c ≤ ). One Katu ≤ Xi ≤ ) such that for each edge e(a, b) labeled by op and ...

  10. poj 3678&lpar;SCC&plus;2-SAT&rpar;

    传送门:Problem 3678 https://www.cnblogs.com/violet-acmer/p/9769406.html 难点: 题意理解+构图 题意: 有n个点 v[0,2..... ...

随机推荐

  1. 想通过加HINT让其走全表扫描

    一个SQL,通过SPM固定它的执行计划,可以通过DBMS_SPM.LOAD_PLANS_FROM_CURSOR_CACHE实现.也可以通地此功能在不修改原SQL的情况下对其加HINT来固定执行计划.D ...

  2. win7如何配置access数据源

    今天想做个管理系统,需要用到数据库,还要设置数据源,可是当我打开控制面板的管理工具的数据源发现只有SQL驱动,找不到access,因为我是用acess做的啊,所以就很郁闷,不过看到了一个方法,好吧,我 ...

  3. Codevs 2296 仪仗队 2008年省队选拔赛山东

    2296 仪仗队 2008年省队选拔赛山东 时间限制: 1 s 空间限制: 256000 KB 题目等级 : 大师 Master 题解 题目描述 Description 作为体育委员,C君负责这次运动 ...

  4. Android窗口管理服务WindowManagerService的简要介绍和学习计划

    在前一个系列文章中,我们从个体的角度来分析了Android应用程序窗口的实现框架.事实上,如果我们从整体的角度来看,Android应用程序窗口的 实现要更复杂,因为它们的类型和作用不同,且会相互影响. ...

  5. StackExchange&period;Redis 使用

    StackExchange.Redis 使用 - 事件(五) 摘要: ConnectionMultiplexer 可以注册如下事件ConfigurationChanged- 配置更改时Configur ...

  6. 201521123017 《Java程序设计》第7周学习总结

    1. 本周学习总结 2. 书面作业 Q1.ArrayList代码分析 1.1 解释ArrayList的contains源代码 1.2 解释E remove(int index)源代码 1.3 结合1. ...

  7. 整理一批 国内外优秀设计团队 &amp&semi; 设计相关网站

    设计做不好,因为看得少!这里精心整理了一批国内外优秀设计团队的官网,以及同设计相关的网站.每个网站,我都浏览了一下,确保里面真的是有干货,并且保持一定的频率正常更新. [腾讯] 腾讯社交用户体验设计 ...

  8. JVM学习九:JVM之GC算法和种类

    我们前面说到了JVM的常用的配置参数,其中就涉及了GC相关的知识,趁热打铁,我们今天就学习下GC的算法有哪些,种类又有哪些,让我们进一步的认识GC这个神奇的东西,帮助我们解决了C 一直挺头疼的内存回收 ...

  9. java中的内部类概念

    内部类和外部类可以互相访问私有属性 1.普通内部类实例化方式 外部类.内部类 对象 = new 外部类().new 内部类(); class Outer{//外部类 private String ms ...

  10. java7 新特性 总结版

    Java7语法新特性: 前言,这是大部分的特性,但还有一些没有写进去,比如多核 并行计算的支持加强 fork join 框架:这方面并没有真正写过和了解.也就不写进来了. 1. switch中增加对S ...