P1955 [NOI2015] 程序自动分析题解

2024-03-14 08:36

本文主要是介绍P1955 [NOI2015] 程序自动分析题解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目

在实现程序自动分析的过程中,常常需要判定一些约束条件是否能被同时满足。

考虑一个约束满足问题的简化版本:假设x1​,x2​,x3​,⋯ 代表程序中出现的变量,给定n个形如xi​=xj​或xi​!=xj​ 的变量相等/不等的约束条件,请判定是否可以分别为每一个变量赋予恰当的值,使得上述所有约束条件同时被满足。例如,一个问题中的约束条件为:x1​=x2​,x2​=x3​,x3​=x4​,x4​!=x1​,这些约束条件显然是不可能同时被满足的,因此这个问题应判定为不可被满足。

现在给出一些约束满足问题,请分别对它们进行判定。

输入输出格式

输入格式

输入的第一行包含一个正整数t,表示需要判定的问题个数。注意这些问题之间是相互独立的。

对于每个问题,包含若干行:

第一行包含一个正整数n,表示该问题中需要被满足的约束条件个数。接下来n行,每行包括三个整数i,j,e,描述一个相等/不等的约束条件,相x邻整数之间用单个空格隔开。若e=1,则该约束条件为xi​=xj​。若e=0,则该约束条件为xi​!=xj​。

输出格式

输出包括t行。

输出文件的第k行输出一个字符串YES或者NO(字母全部大写),YES表示输入中的第k个问题判定为可以被满足,NO表示不可被满足。

输入输出样例

输入样例

2
2
1 2 1
1 2 0
2
1 2 1
2 1 1

输出样例

NO
YES

解析

这个题目采用并查集解决,先根据e值的大小将式子进行排序,先处理相等的式子,将相等的式子合并在一个集合里面,然后处理不等的式子,如果不等的式子出现在同一个集合里面,那么直接返回NO,如果没有返回YES。这个题目由于数据比较大,所以将数据离散化将空间进行压缩。

#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
const int max_n=200005;
struct node{int l,r,e;
}m[100005];
int f[max_n];
bool cmp(node a,node b){return a.e>b.e;
}
int find(int x){if(f[x]!=x){f[x]=find(f[x]);}return f[x];
}
void ad(int x,int y){x=find(x);y=find(y);if(x==y){return;}f[x]=y;
}
void judge(){int n,mark=1;//使用mark进行离散化数据压缩空间scanf("%d",&n);map<int,int> ds;for(int i=1;i<=n;i++){scanf("%d%d%d",&m[i].l,&m[i].r,&m[i].e);if(!ds[m[i].l]){ds[m[i].l]=mark;mark++;}if(!ds[m[i].r]){ds[m[i].r]=mark;mark++;}}sort(m+1,m+1+n,cmp);for(int i=1;i<=n;i++){if(m[i].e){ad(ds[m[i].l],ds[m[i].r]);}else{if(find(ds[m[i].l])==find(ds[m[i].r])){printf("NO\n");return;}}}printf("YES\n");
}
int main(){int t;scanf("%d",&t);while(t--){for(int i=1;i<=max_n;i++){f[i]=i;}judge();}return 0;
}

这篇关于P1955 [NOI2015] 程序自动分析题解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/807822

相关文章

将Java程序打包成EXE文件的实现方式

《将Java程序打包成EXE文件的实现方式》:本文主要介绍将Java程序打包成EXE文件的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录如何将Java程序编程打包成EXE文件1.准备Java程序2.生成JAR包3.选择并安装打包工具4.配置Launch4

Java程序进程起来了但是不打印日志的原因分析

《Java程序进程起来了但是不打印日志的原因分析》:本文主要介绍Java程序进程起来了但是不打印日志的原因分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java程序进程起来了但是不打印日志的原因1、日志配置问题2、日志文件权限问题3、日志文件路径问题4、程序

Java字符串操作技巧之语法、示例与应用场景分析

《Java字符串操作技巧之语法、示例与应用场景分析》在Java算法题和日常开发中,字符串处理是必备的核心技能,本文全面梳理Java中字符串的常用操作语法,结合代码示例、应用场景和避坑指南,可快速掌握字... 目录引言1. 基础操作1.1 创建字符串1.2 获取长度1.3 访问字符2. 字符串处理2.1 子字

IDEA自动生成注释模板的配置教程

《IDEA自动生成注释模板的配置教程》本文介绍了如何在IntelliJIDEA中配置类和方法的注释模板,包括自动生成项目名称、包名、日期和时间等内容,以及如何定制参数和返回值的注释格式,需要的朋友可以... 目录项目场景配置方法类注释模板定义类开头的注释步骤类注释效果方法注释模板定义方法开头的注释步骤方法注

pytorch自动求梯度autograd的实现

《pytorch自动求梯度autograd的实现》autograd是一个自动微分引擎,它可以自动计算张量的梯度,本文主要介绍了pytorch自动求梯度autograd的实现,具有一定的参考价值,感兴趣... autograd是pytorch构建神经网络的核心。在 PyTorch 中,结合以下代码例子,当你

Python如何自动生成环境依赖包requirements

《Python如何自动生成环境依赖包requirements》:本文主要介绍Python如何自动生成环境依赖包requirements问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑... 目录生成当前 python 环境 安装的所有依赖包1、命令2、常见问题只生成当前 项目 的所有依赖包1、

Python 迭代器和生成器概念及场景分析

《Python迭代器和生成器概念及场景分析》yield是Python中实现惰性计算和协程的核心工具,结合send()、throw()、close()等方法,能够构建高效、灵活的数据流和控制流模型,这... 目录迭代器的介绍自定义迭代器省略的迭代器生产器的介绍yield的普通用法yield的高级用法yidle

SpringBoot实现微信小程序支付功能

《SpringBoot实现微信小程序支付功能》小程序支付功能已成为众多应用的核心需求之一,本文主要介绍了SpringBoot实现微信小程序支付功能,文中通过示例代码介绍的非常详细,对大家的学习或者工作... 目录一、引言二、准备工作(一)微信支付商户平台配置(二)Spring Boot项目搭建(三)配置文件

C++ Sort函数使用场景分析

《C++Sort函数使用场景分析》sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变,如果某些场景需要保持相同元素间的相对顺序,可使... 目录C++ Sort函数详解一、sort函数调用的两种方式二、sort函数使用场景三、sort函数排序

Spring Boot项目中结合MyBatis实现MySQL的自动主从切换功能

《SpringBoot项目中结合MyBatis实现MySQL的自动主从切换功能》:本文主要介绍SpringBoot项目中结合MyBatis实现MySQL的自动主从切换功能,本文分步骤给大家介绍的... 目录原理解析1. mysql主从复制(Master-Slave Replication)2. 读写分离3.