`
Simone_chou
  • 浏览: 195925 次
  • 性别: Icon_minigender_2
  • 来自: 广州
社区版块
存档分类
最新评论

Katu Puzzle(2 - sat)

    博客分类:
  • POJ
 
阅读更多
Katu Puzzle
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 7395   Accepted: 2720

Description

Katu Puzzle is presented as a directed graph G(VE) with each edge e(a, b) labeled by a boolean operator op (one of AND, OR, XOR) and an integer c (0 ≤ c ≤ 1). One Katu is solvable if one can find each vertex Vi a value Xi (0 ≤ X≤ 1) such that for each edge e(a, b) labeled by op and c, the following formula holds:

 Xa op Xb = c

The calculating rules are:

AND 0 1
0 0 0
1 0 1
OR 0 1
0 0 1
1 1 1
XOR 0 1
0 0 1
1 1 0

Given a Katu Puzzle, your task is to determine whether it is solvable.

Input

The first line contains two integers N (1 ≤ N ≤ 1000) and M,(0 ≤ M ≤ 1,000,000) indicating the number of vertices and edges.
The following M lines contain three integers (0 ≤ a < N), b(0 ≤ b < N), c and an operator op each, describing the edges.

Output

Output a line containing "YES" or "NO".

Sample Input

4 4
0 1 1 AND
1 2 1 OR
3 2 0 AND
3 0 0 XOR

Sample Output

YES

Hint

X0 = 1, X1 = 1, X2 = 0, X3 = 1.

       题意:

       给出 N (1 ~ 1000)和 M (0 ~ 1000000),代表有 N 个命题,M 条关系式。后给出 M 条关系式是什么。问能否找到一组命题的解,满足所有的关系式。

 

       思路:

       2 - sat。根据给出的关系式,将可以确定的关系进行建图。比如 a & b = 1,则 a == 1 -> b == 1,b == 1 -> a == 1,若 a == 0 或者 b == 0,则无论如何都不可能满足条件式,所以要把矛盾的条件也要进行建图,建图方法为 a == 0 -> a== 1,b == 0 -> b == 1。对 | 的情况也是如此,对于 ^ 则没有矛盾的情况。建图后判断一个命题的真和假有没有在同一个强连通分量即可。并且用 STL 的 vector 容器存邻接表。

 

      AC:

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stack>
#include <vector>

using namespace std;

const int NMAX = 1005 * 2;
const int EMAX = 1000000 * 2;

int n, m;
vector<int> v[NMAX];

int dfs_clock, scc_cnt;
int pre[NMAX], low[NMAX], cmp[NMAX];
stack<int> s;

void dfs(int u) {
        pre[u] = low[u] = ++dfs_clock;
        s.push(u);

        for (int i = 0; i < v[u].size(); ++i) {
                if (!pre[ v[u][i] ]) {
                        dfs( v[u][i] );
                        low[u] = min(low[u], low[ v[u][i] ]);
                } else if (!cmp[ v[u][i] ]) {
                        low[u] = min(low[u], pre[ v[u][i] ]);
                }
        }

        if (low[u] == pre[u]) {
                ++scc_cnt;
                for (;;) {
                        int x = s.top(); s.pop();
                        cmp[x] = scc_cnt;
                        if (x == u) break;
                }
        }
}

void scc() {
        dfs_clock = scc_cnt = 0;
        memset(pre, 0, sizeof(pre));
        memset(cmp, 0, sizeof(cmp));

        for (int u = 0; u < 2 * n; ++u) {
                if (!pre[u]) dfs(u);
        }
}

void add_edge (int a, int b, int ans, char *res) {
        if (!strcmp(res, "AND")) {
                if (!ans) {
                        v[a].push_back(n + b);
                        v[b].push_back(n + a);
                } else {
                        v[a].push_back(b);
                        v[b].push_back(a);
                        v[n + a].push_back(a); //矛盾情况
                        v[n + b].push_back(b); //矛盾情况
                }
        } else if (!strcmp(res, "OR")) {
                if (!ans) {
                        v[n + a].push_back(n + b);
                        v[n + b].push_back(n + a);
                        v[a].push_back(n + a); //矛盾情况
                        v[b].push_back(n + b); //矛盾情况
                } else {
                        v[n + a].push_back(b);
                        v[n + b].push_back(a);
                }
        } else if (!strcmp(res, "XOR")) {
                if (!ans) {
                        v[a].push_back(b);
                        v[b].push_back(a);
                        v[n + a].push_back(n + b);
                        v[n + b].push_back(n + a);
                } else {
                        v[a].push_back(n + b);
                        v[b].push_back(n + a);
                        v[n + a].push_back(b);
                        v[n + b].push_back(a);
                }
        }
}

int main() {

        scanf("%d%d", &n, &m);
        while (m--) {
                int a, b, ans;
                char res[5];
                scanf("%d%d%d%s", &a, &b, &ans, res);
                add_edge(a, b, ans, res);
        }

        scc();

        for (int i = 0; i < n; ++i) {
                if (cmp[i] == cmp[n + i]) {
                        printf("NO\n");
                        return 0;
                }
        }

        printf("YES\n");

        return 0;
}

  

 

 

 

分享到:
评论

相关推荐

    lpSolve线性规划c库

    《lpSolve线性规划C库详解》 线性规划是一种优化方法,广泛应用于工程、经济、管理等领域,用于寻找一组变量的最大值或最小值,这些变量受到一系列线性等式和不等式的约束。lpSolve是这样一个开源库,它提供了一套...

    电动汽车充电站选址定容优化:基于MATLAB建模求解与成本最小化策略,电动汽车充电站选址定容优化:基于MATLAB的最优规划模型及初学者指南,电动汽车充电站的最优选址定容MATLAB程序 以规划期内充

    电动汽车充电站选址定容优化:基于MATLAB建模求解与成本最小化策略,电动汽车充电站选址定容优化:基于MATLAB的最优规划模型及初学者指南,电动汽车充电站的最优选址定容MATLAB程序 以规划期内充电站的总成本 (包括投资、运行和维护成本)和网损费用之和最小为目标,考虑了相关的约束条件,构造了电动汽车充电站最优规划的数学模型。 从34个位置中,选取7个充电站地址,进行选址优化 关键词:电动汽车;充电站;选址和定容 程序注释清晰,适合初学者学习 ,电动汽车; 充电站选址定容; MATLAB程序; 规划模型; 成本优化; 网损费用; 初学者学习; 程序注释清晰,基于MATLAB的电动汽车充电站选址定容优化程序:成本最小化与约束条件下的选址策略

    基于源荷双重不确定性的虚拟电厂日前鲁棒经济调度优化模型基于MATLAB+CPLEX仿真平台求解,基于源荷双重不确定性的虚拟电厂日前鲁棒优化经济调度策略,MATLAB代码:计及源-荷双重不确定性的电厂日

    基于源荷双重不确定性的虚拟电厂日前鲁棒经济调度优化模型基于MATLAB+CPLEX仿真平台求解,基于源荷双重不确定性的虚拟电厂日前鲁棒优化经济调度策略,MATLAB代码:计及源-荷双重不确定性的电厂日前鲁棒优化调度 关键词:电厂 微网调度 鲁棒调度 源荷不确定性 日前经济调度 参考文档:《含电动汽车和风电机组的发电厂竞价策略_杨甲甲》参考其鲁棒模型的化简求解部分,即附录中的鲁棒问题化简求解的全过程; 《Virtual power plant mid-term dispatch optimization》参考燃气轮机、储能部分模型 仿真平台:MATLAB+CPLEX 主要内容:代码主要做的是一个电厂或者微网单元的日前鲁棒经济调度的模型,考虑了光伏出力和负荷功率的双重不确定性,采用鲁棒优化法处理不确定性变量,构建了电厂鲁棒优化调度模型。 具体来看,不确定性考虑的是目标函数以及约束条件中均含有不确定变量,设置鲁棒系数可以调节多重不确定结果,化简的过程也很清晰,程序实现效果良好,一行一注释。 ,关键词:虚拟电厂; 鲁棒优化调度; 源荷不确定性; 日前经济调度; 微网调度; 光伏出力

    基于遗传算法的储能优化配置研究:成本模型分析与最优运行计划求解(含风光机组),基于遗传算法的储能优化配置:成本模型分析与最优运行计划求解(含风光机组),MATLAB代码:基于遗传算法的储能优化配置(可

    基于遗传算法的储能优化配置研究:成本模型分析与最优运行计划求解(含风光机组),基于遗传算法的储能优化配置:成本模型分析与最优运行计划求解(含风光机组),MATLAB代码:基于遗传算法的储能优化配置(可加入风光机组) 关键词:储能优化配置 遗传算法 储能充放电优化 参考文档:无明显参考文档,仅有几篇文献可以适当参考 仿真平台:MATLAB 平台采用遗传算法实现求解 优势:代码注释详实,适合参考学习,非目前烂大街的版本,程序非常精品,请仔细辨识 主要内容:建立了储能的成本模型,包含运行维护成本以及容量配置成本,然后以该成本函数最小为目标函数,经过遗传算法求解出其最优运行计划,并通过其运行计划最终确定储能容量配置的大小,求解采用的是遗传算法,求解效果极佳,具体可以看图 ,关键词:MATLAB代码;遗传算法;储能优化配置;储能充放电优化;成本模型;运行维护成本;容量配置成本;最优运行计划;求解效果。,基于遗传算法的储能优化配置MATLAB代码:精细优化与成本最小化研究

    设计模式- 观察者模式 Observer Pattern详解

    如本文所描述,设计模式经典实现、三种其他实现方式以及六个方向的问题优化的详细代码

    高性能DSP28335驱动的移相全桥同步整流技术:高效电源输出与轻量级结构设计,基于DSP28335的高效同步整流电源系统:移相全桥驱动,低损耗输出近94%效率,铝基板+平面变压器设计挑战与低成本方案

    高性能DSP28335驱动的移相全桥同步整流技术:高效电源输出与轻量级结构设计,基于DSP28335的高效同步整流电源系统:移相全桥驱动,低损耗输出近94%效率,铝基板+平面变压器设计挑战与低成本方案探索,自研DSP28335+移相全桥+纯程序实现同步整流。 目前在DSP固有损耗2W的情况下,输出120W效率接近94%。 就是铝基板+平面变压器玩起来太贵,不好做小批量,335现在也很贵。 基于035的低成本版本近期开始设计~~~ 数字电源demo,输入18-32V,输出12V15A,伍尔特电感+平面变压器+板上平面变压器辅助电源,隔离半桥驱动+隔离采样,用于技术交流和样机平台搭建。 采用上下叠板架构,上板为4层DSP控制板,下板为单层功率铝基板,散热极佳。 ,自研DSP28335; 移相全桥; 纯程序同步整流; 效率接近94%; 低成本版本设计; 数字电源demo; 上下叠板架构; DSP控制板; 散热。,自研DSP28335控制下的同步整流技术优化:效率接近94%的电源解决方案

    PPT模板 -星际郎中:守护星际生命.pptx

    PPT模板 -星际郎中:守护星际生命.pptx

    19考试真题最近的t41.txt

    19考试真题最近的t41.txt

    Xilinx ug476-7Series-Transceivers

    Xilinx公司推出的7系列FPGA中的GTX/GTH收发器是用于高速串行通信的收发器模块,能够实现数据的高速串行传输。本资料为Xilinx提供的用户手册ug476_7Series_Transceivers

    GearTrain 提供了灵活的推理框架, 支持视频、图片推理方式 基于 GearTrain 用户可像齿轮一样自由组合各种Pipeline,实现各种推理任务

    GearTrain 提供了灵活的推理框架, 支持视频、图片推理方式。基于 GearTrain 用户可像齿轮一样自由组合各种Pipeline,实现各种推理任务

    一个测试的网页布局,作为备份

    一个测试的网页布局,作为备份

    基于SSM+redis的awd对抗系统 .zip(毕设&课设&实训&大作业&竞赛&项目)

    项目工程资源经过严格测试运行并且功能上ok,可实现复现复刻,拿到资料包后可实现复现出一样的项目,本人系统开发经验充足(全栈全领域),有任何使用问题欢迎随时与我联系,我会抽时间努力为您解惑,提供帮助 【资源内容】:包含源码+工程文件+说明等。答辩评审平均分达到96分,放心下载使用!可实现复现;设计报告也可借鉴此项目;该资源内项目代码都经过测试运行,功能ok 【项目价值】:可用在相关项目设计中,皆可应用在项目、毕业设计、课程设计、期末/期中/大作业、工程实训、大创等学科竞赛比赛、初期项目立项、学习/练手等方面,可借鉴此优质项目实现复刻,设计报告也可借鉴此项目,也可基于此项目来扩展开发出更多功能 【提供帮助】:有任何使用上的问题欢迎随时与我联系,抽时间努力解答解惑,提供帮助 【附带帮助】:若还需要相关开发工具、学习资料等,我会提供帮助,提供资料,鼓励学习进步 下载后请首先打开说明文件(如有);整理时不同项目所包含资源内容不同;项目工程可实现复现复刻,如果基础还行,也可在此程序基础上进行修改,以实现其它功能。供开源学习/技术交流/学习参考,勿用于商业用途。质量优质,放心下载使用,资源为网络商品(电子资料类)基于网络商品和电子资料商品的性质和特征不支持退款,质量优质,放心下载使用

    内蒙古自治区公共数据资源登记管理暂行办法.docx

    内蒙古自治区公共数据资源登记管理暂行办法.docx

    MATLAB下基于遗传算法的有序充放电优化策略:实现电动汽车充电费用最低与负荷峰谷平衡,基于遗传算法的电动汽车有序充放电优化策略:精英自适应混合算法实现负荷均衡与费用最小化,MATLAB代码:基于遗传

    MATLAB下基于遗传算法的有序充放电优化策略:实现电动汽车充电费用最低与负荷峰谷平衡,基于遗传算法的电动汽车有序充放电优化策略:精英自适应混合算法实现负荷均衡与费用最小化,MATLAB代码:基于遗传算法的电动汽车有序充放电优化 关键词:遗传算法 电动汽车 有序充电 优化调度 参考文档:《精英自适应混合遗传算法及其实现_江建》算法部分;电动汽车建模部分相关文档太多,自行搜索参考即可; 仿真平台:MATLAB 主要内容:代码主要做的是利用遗传算法对电动汽车有序充电进行优化;优化目标包括充电费用最低,充电时间达到要求(电动汽车充到足够的电)考虑电动汽车充电对电网负荷的影响,使负荷峰谷差最小。 分别利用传统、精英和变异遗传算法进行对比算法优劣,比较迭代结果,优化变量为起始充电时刻 ,关键词:MATLAB代码; 遗传算法; 电动汽车; 有序充电; 优化调度; 充电费用; 充电时间; 电网负荷; 精英自适应混合遗传算法; 迭代结果; 优化变量。,基于遗传算法的电动汽车有序充放电优化调度策略研究

    基于OpenCV的车牌识别系统的设计与实现.zip(毕设&课设&实训&大作业&竞赛&项目)

    项目工程资源经过严格测试运行并且功能上ok,可实现复现复刻,拿到资料包后可实现复现出一样的项目,本人系统开发经验充足(全栈全领域),有任何使用问题欢迎随时与我联系,我会抽时间努力为您解惑,提供帮助 【资源内容】:包含源码+工程文件+说明等。答辩评审平均分达到96分,放心下载使用!可实现复现;设计报告也可借鉴此项目;该资源内项目代码都经过测试运行,功能ok 【项目价值】:可用在相关项目设计中,皆可应用在项目、毕业设计、课程设计、期末/期中/大作业、工程实训、大创等学科竞赛比赛、初期项目立项、学习/练手等方面,可借鉴此优质项目实现复刻,设计报告也可借鉴此项目,也可基于此项目来扩展开发出更多功能 【提供帮助】:有任何使用上的问题欢迎随时与我联系,抽时间努力解答解惑,提供帮助 【附带帮助】:若还需要相关开发工具、学习资料等,我会提供帮助,提供资料,鼓励学习进步 下载后请首先打开说明文件(如有);整理时不同项目所包含资源内容不同;项目工程可实现复现复刻,如果基础还行,也可在此程序基础上进行修改,以实现其它功能。供开源学习/技术交流/学习参考,勿用于商业用途。质量优质,放心下载使用,资源为网络商品(电子资料类)基于网络商品和电子资料商品的性质和特征不支持退款

    STM32开发:IIR带阻滤波器设计与实现,含巴特沃斯和切比雪夫滤波器MATLAB程序,STM32开发中IIR带阻滤波器的实现与巴特沃斯滤波器设计详解:附MATLAB程序,STM32开发 IIR带阻滤

    STM32开发:IIR带阻滤波器设计与实现,含巴特沃斯和切比雪夫滤波器MATLAB程序,STM32开发中IIR带阻滤波器的实现与巴特沃斯滤波器设计详解:附MATLAB程序,STM32开发 IIR带阻滤波器 STM32实现IIR无限冲击响应带阻滤波器设计,巴特沃斯滤波器,代码工整,自编代码,注释详细,赠送巴特沃斯和切比雪夫IIR带阻滤波器MATLAB程序 ,STM32开发; IIR带阻滤波器; 无限冲击响应; 巴特沃斯滤波器; 自编代码; 注释详细; MATLAB程序,STM32中IIR带阻滤波器设计与实现

    电商系统(包含手机端,前端,后端).zip(毕设&课设&实训&大作业&竞赛&项目)

    项目工程资源经过严格测试运行并且功能上ok,可实现复现复刻,拿到资料包后可实现复现出一样的项目,本人系统开发经验充足(全栈全领域),有任何使用问题欢迎随时与我联系,我会抽时间努力为您解惑,提供帮助 【资源内容】:包含源码+工程文件+说明等。答辩评审平均分达到96分,放心下载使用!可实现复现;设计报告也可借鉴此项目;该资源内项目代码都经过测试运行,功能ok 【项目价值】:可用在相关项目设计中,皆可应用在项目、毕业设计、课程设计、期末/期中/大作业、工程实训、大创等学科竞赛比赛、初期项目立项、学习/练手等方面,可借鉴此优质项目实现复刻,设计报告也可借鉴此项目,也可基于此项目来扩展开发出更多功能 【提供帮助】:有任何使用上的问题欢迎随时与我联系,抽时间努力解答解惑,提供帮助 【附带帮助】:若还需要相关开发工具、学习资料等,我会提供帮助,提供资料,鼓励学习进步 下载后请首先打开说明文件(如有);整理时不同项目所包含资源内容不同;项目工程可实现复现复刻,如果基础还行,也可在此程序基础上进行修改,以实现其它功能。供开源学习/技术交流/学习参考,勿用于商业用途。质量优质,放心下载使用,资源为网络商品(电子资料类)基于网络商品和电子资料商品的性质和特征不支持退款,质量优质,放心下载使用

    机器学习【KMeans聚类分析实战】用户分群聚类详解-SSE、CH 指数、SC全解析,实战电信客户分群案例

    包含输入输出,可视化案例。聚类算法

    基于PLC的地铁排水控制系统设计:梯形图程序、接线图与IO分配组态全解析,基于PLC的地铁排水控制系统设计:梯形图程序、接线图与IO分配组态全解析,No.505 基于PLC的地铁排水控制系统设计电气控

    基于PLC的地铁排水控制系统设计:梯形图程序、接线图与IO分配组态全解析,基于PLC的地铁排水控制系统设计:梯形图程序、接线图与IO分配组态全解析,No.505 基于PLC的地铁排水控制系统设计电气控制程序 带解释的梯形图程序,接线图原理图图纸,io分配,组态画面 ,505; PLC地铁排水控制; 电气控制程序; 梯形图程序; 接线图原理图; IO分配; 组态画面,PLC驱动的地铁排水系统设计:电气控制程序详解及图解

Global site tag (gtag.js) - Google Analytics