stdKonjac's Blog

An AC a day keeps the WA away ~

【NOI2015 程序自动分析】

题目背景

NOI2015 DAY1 T1

题目描述

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

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

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

输入格式

第 1 行包含 1 个正整数 t ,表示需要判定的问题个数。注意这些问题之间是相互独立的。
对于每个问题,包含若干行:
第 1 行包含 1 个正整数 n ,表示该问题中需要被满足的约束条件个数。
接下来 n 行,每行包括 3 个整数 i,j,e ,描述 1 个相等/不等的约束条件,相邻整数之间用单个空格隔开。若 e=1 ,则该约束条件为 xi=xj ;若 e=0 ,则该约束条件为 xi≠xj 。

输出格式

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

样例数据 1

输入

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

输出

NO
YES

样例数据 2

输入

2
3
1 2 1
2 3 1
3 1 1
4
1 2 1
2 3 1
3 4 1
1 4 0

输出

YES
NO

备注

【样例1说明】
在第一个问题中,约束条件为:x1=x2,x1≠x2 。这两个约束条件互相矛盾,因此不可被同时满足。
在第二个问题中,约束条件为:x1=x2,x2=x1 。这两个约束条件是等价的,可以被同时满足。

【样例2说明】
在第一个问题中,约束条件有三个:x1=x2,x2=x3,x3=x1 。只需赋值使得 x1=x2=x3 ,即可同时满足所有的约束条件。
在第二个问题中,约束条件有四个:x1=x2,x2=x3,x3=x4,x1≠x4 。由前三个约束条件可以推出 x1=x2=x3=x4 ,然而最后一个约束条件却要求 x1≠x4 ,因此不可被满足。

【数据范围】

《【NOI2015 程序自动分析】》

 

一道挂着NOI牌子的NOIP题……把所有相等的数都用并查集划分到一个集合里,之后再在不等条件里面找,看是否有已经分到统一集合(相等)的点,如果有,就输出NO否则输出YES,最后3个点要进行离散化,先把出现过的点排个序,然后unique去重(懒得手写去重了)用map开个数组存这个数对应离散化后的数是多少即可。

然而,我考试的时候写了个蒟蒻的Tarjan结果只有90分,最后一个点递归爆栈了QAQ再次证明了我有多么蒟蒻……

下面是代码:

 

点赞

发表评论

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

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.