公司网站建设费用怎么记账,微信公众平台登录界面,桂林微信网站开发,wordpress 插件有后门题目描述
在实现程序自动分析的过程中,常常需要判定一些约束条件是否能被同时满足。
考虑一个约束满足问题的简化版本#xff1a;假设 x1,x2,x3,…#xfffd;1,#xfffd;2,#xfffd;3,… 代表程序中出现的变量#xff0c;给定n#xfffd;个形如xixj#x… 题目描述
在实现程序自动分析的过程中,常常需要判定一些约束条件是否能被同时满足。
考虑一个约束满足问题的简化版本假设 x1,x2,x3,…1,2,3,… 代表程序中出现的变量给定n个形如xixj或xi≠xj≠ 的变量相等/不等的约束条件请判定是否可以分别为每一个变量赋予恰当的值使得上述所有约束条件同时被满足。
例如一个问题中的约束条件为x1x2x2x3x3x4x1≠x41223341≠4这些约束条件显然是不可能同时被满足的因此这个问题应判定为不可被满足。
现在给出一些约束满足问题请分别对它们进行判定。 输入
输入文件的第11行包含11个正整数t表示需要判定的问题个数。注意这些问题之间是相互独立的。
对于每个问题包含若干行
第11行包含11个正整数n表示该问题中需要被满足的约束条件个数。
接下来n行每行包括33个整数i,j,e,,描述11个相等/不等的约束条件相邻整数之间用单个空格隔开。若e11则该约束条件为xixj若e00则该约束条件为xi≠xj≠。
输出
输出文件包括t行。
输出文件的第11行输出一个字符串“YES”或者“NO”不包含引号字母全部大写“YES”表示当前问题判定为可以被满足“NO”表示不可被满足。
输入样例1
2
2
1 2 1
1 2 0
2
1 2 1
2 1 1
输出样例1
NO
YES
#include iostream
#include vector
#include algorithm
#include unordered_map
using namespace std;
class UnionSet {
public:UnionSet(int n) : fa(n 1) {for (int i 0; i n; i) fa[i] i;}int get(int x) {return fa[x] (fa[x] x ? x : fa[x]);}void merge(int a, int b) {fa[get(a)] get(b);return;}vectorint fa;
};struct Dara {int i, j, e;
};
void solve() {int n, cnt 0;cin n;vectorDara arr(n);unordered_mapint, int h;for (int i 0; i n; i) {cin arr[i].i arr[i].j arr[i].e;if (h.find(arr[i].i) h.end()) h[arr[i].i] cnt;if (h.find(arr[i].j) h.end()) h[arr[i].j] cnt;}UnionSet u(2 * n);for (int i 0; i n; i) {if (arr[i].e 0) continue;u.merge(h[arr[i].i], h[arr[i].j]);}int flag 1;for (int i 0; i n flag; i) {if (arr[i].e 1) continue;if (u.get(h[arr[i].i]) u.get(h[arr[i].j])) {flag 0;}}if (flag) cout YES endl;else cout NO endl;return;
}
int main() {int m;cin m;while (m--) {solve();}return 0;
}
