巨鹿网站建设设计,昌大建设集团地址,网站头部模板,国外科技类网站在实现程序自动分析的过程中#xff0c;常常需要判定一些约束条件是否能被同时满足。考虑一个约束满足问题的简化版本#xff1a;假设 x1,x2,x3,… 代表程序中出现的变量#xff0c;给定 n 个形如 xixj 或 xi≠xj 的变量相等/不等的约束条件#xff0c;请判定是否可以分别为…在实现程序自动分析的过程中常常需要判定一些约束条件是否能被同时满足。考虑一个约束满足问题的简化版本假设 x1,x2,x3,… 代表程序中出现的变量给定 n 个形如 xixj 或 xi≠xj 的变量相等/不等的约束条件请判定是否可以分别为每一个变量赋予恰当的值使得上述所有约束条件同时被满足。 例如一个问题中的约束条件为x1x2x2x3x3x4x1≠x4这些约束条件显然是不可能同时被满足的因此这个问题应判定为不可被满足。 现在给出一些约束满足问题请分别对它们进行判定。
输入格式 输入文件的第 1 行包含 1 个正整数 t表示需要判定的问题个数注意这些问题之间是相互独立的。 对于每个问题包含若干行第 1 行包含 1 个正整数 n表示该问题中需要被满足的约束条件个数。 接下来 n 行每行包括 3 个整数 i,j,e描述 1 个相等/不等的约束条件相邻整数之间用单个空格隔开。若 e1则该约束条件为 xixj若 e0则该约束条件为 xi≠xj。
输出格式 输出文件包括 t 行。 输出文件的第 k 行输出一个字符串 YES 或者 NOYES 表示输入中的第 k 个问题判定为可以被满足NO 表示不可被满足。
数据范围 1≤n≤105, 1≤i,j≤109
输入样例 2 2 1 2 1 1 2 0 2 1 2 1 2 1 1
输出样例 NO YES
解析
每个问题给的条件是相互独立的也就是和顺序无关可先进行“e1” 再进行“e2”。
当进行“e1”时是并查集的合并
当进行“e2”时也就是相当于变相的并查集查询。
#include bits/stdc.h
using namespace std;
#define int long long
const int N2e610;
int p[N];
map int,int k;
int cnt;
int get(int x)
{if (k.count(x)0) k[x]cnt; //离散化return k[x];
}
int find(int x)
{if (x!p[x]) p[x]find(p[x]);return p[x];
}
struct node
{int a,b,e;
}s[N];
bool cmp(node x,node y)
{return x.ey.e;
}
signed main()
{int t;scanf(%lld,t); //读入的数据较多用scanf读入while (t--){int n;scanf(%lld,n);for (int i1;i2e6;i) p[i]i;k.clear(); //记得要清空哦cnt0;for (int i0;in;i) {int x,y;scanf(%lld%lld%lld,x,y,s[i].e); s[i].aget(x); //离散化map即可s[i].bget(y); }bool falg0;for (int i0;in;i)if (s[i].e1){if (find(s[i].a)!find(s[i].b)) p[find(s[i].a)]find(s[i].b);}for (int i0;in;i)if (s[i].e0){if (find(s[i].a)find(s[i].b)) {falg1;break;}}if (!falg) puts(YES);else puts(NO);}return 0;
}
