题目描述
在实现程序自动分析的过程中,常常需要判定一些约束条件是否能被同时满足。
考虑一个约束满足问题的简化版本:假设 x_1,x_2,x_3,\cdotsx1,x2,x3,⋯ 代表程序中出现的变量,给定 nn 个形如 x_i=x_jxi=xj或 x_i\neq x_jxi=xj 的变量相等/不等的约束条件,请判定是否可以分别为每一个变量赋予恰当的值,使得上述所有约束条件同时被满足。例如,一个问题中的约束条件为:x_1=x_2,x_2=x_3,x_3=x_4,x_4\neq x_1x1=x2,x2=x3,x3=x4,x4=x1,这些约束条件显然是不可能同时被满足的,因此这个问题应判定为不可被满足。
现在给出一些约束满足问题,请分别对它们进行判定。
输入格式
输入的第一行包含一个正整数 tt,表示需要判定的问题个数。注意这些问题之间是相互独立的。
对于每个问题,包含若干行:
第一行包含一个正整数 nn,表示该问题中需要被满足的约束条件个数。接下来 nn 行,每行包括三个整数 i,j,ei,j,e,描述一个相等/不等的约束条件,相邻整数之间用单个空格隔开。若 e=1e=1,则该约束条件为 x_i=x_jxi=xj。若e=0e=0,则该约束条件为 x_i\neq x_jxi=xj。
输出格式
输出包括 tt 行。
输出文件的第 kk 行输出一个字符串
YES
或者NO
(字母全部大写),YES
表示输入中的第 kk 个问题判定为可以被满足,NO
表示不可被满足。输入输出样例
输入 #1复制
2 2 1 2 1 1 2 0 2 1 2 1 2 1 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输出 #2复制
YES NO说明/提示
【样例解释1】
在第一个问题中,约束条件为:x_1=x_2,x_1\neq x_2x1=x2,x1=x2。这两个约束条件互相矛盾,因此不可被同时满足。
在第二个问题中,约束条件为:x_1=x_2,x_1 = x_2x1=x2,x1=x2。这两个约束条件是等价的,可以被同时满足。
【样例说明2】
在第一个问题中,约束条件有三个:x_1=x_2,x_2= x_3,x_3=x_1x1=x2,x2=x3,x3=x1。只需赋值使得 x_1=x_2=x_3x1=x2=x3,即可同时满足所有的约束条件。
在第二个问题中,约束条件有四个:x_1=x_2,x_2= x_3,x_3=x_4,x_4\neq x_1x1=x2,x2=x3,x3=x4,x4=x1。由前三个约束条件可以推出 x_1=x_2=x_3=x_4x1=x2=x3=x4,然而最后一个约束条件却要求 x_1\neq x_4x1=x4,因此不可被满足。
【数据范围】
注:实际上 n\le 10^6n≤106 。
1.首先,此题的数据范围i,j很大,1e9的范围, 而n的范围 <= 1e6,每个n对应两个点,所以总共使用到的数据不会超过 2e6。而此种情况,便可以想到需要使用离散化。
2.而离散化的时候,有两种离散化的情况,
(1)离散化后需要保序,也就是需要原先x < y, 离散化后 get(x) < get(y),
这种方式就是之前学过的,先sort 。 然后 e.erase(unique( e.begin(),e.end() ), e.end() ).
(2)离散化后不需要保序, 则可以直接使用哈希 unordered_map<int,int> q.
判断这个值x是否再哈希中,q.count(x), 如果再,直接return q[x];
如果不在 q[x] = ++idx;
return q[x];
离散化了x1,x2后,就需要判断是否所给条件矛盾。
而我们可以发现,
先给出的条件得到,a 与 b 相等后。 再给出 a 与 b 不相等。矛盾
先给出的条件得到,a 与 b 不相等后, 再给出a 与 b 相等, 也矛盾
也就是矛盾的情况,与给出的条件的顺序无关。
那么我们就可以先完成所有给出的条件中,相等的情况。 因为 得到a,b相等之后 再给出a,b不相等则矛盾容易判断。
而a,b相等直接让它们再同一集合中, a,b不相等则不在同一集合中。
那么矛盾的情况就是a,b已经再同一集合中了,你现在却说要a,b不在同一集合中。
这就用到了并查集的,合并 和 查询 操作。
# include <iostream> # include <unordered_map> using namespace std; const int N = 2e6 + 10; int p[N]; int n; unordered_map <int,int> h; int idx = 0; struct edg { int a,b,e; } edg[N]; int get(int x) { if(!h.count(x)) { h[x] = ++idx; } return h[x]; } int find2(int x) { if(p[x] != x) { p[x] = find2(p[x]); } return p[x]; } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d",&n); h.clear(); idx = 0; // 此两行清空上一次测试数据的影响。 for(int i = 1 ; i <= n ; i++) { int x,y,z; scanf("%d %d %d",&x,&y,&z); edg[i] = {get(x),get(y),z}; } for(int i = 1 ; i <= 2 * n ; i++) { p[i] = i; } for(int i = 1; i <= n ; i++) { if(edg[i].e == 1) { int temp1 = find2(edg[i].a); int temp2 = find2(edg[i].b); p[temp1] = temp2; } } bool flag = true; for(int i = 1 ; i <= n ; i++) { if(edg[i].e == 0) { int temp1 = find2(edg[i].a); int temp2 = find2(edg[i].b); if(temp1 == temp2) { flag = false; break; } } } if(flag) { printf("YES\n"); } else { printf("NO\n"); } } return 0; }