【问题描述】
在实现程序自动分析的过程中,常常需要判定一些约束条件是否能被同时满足。
考虑一个约束满足问题的简化版本:假设 x 1 , x 2 , x 3 , ⋯ 代表程序中出现的变量,给定 n 个形如 x i = x j 或 x i ≠ x j 的变量相等/不等的约束条件,请判定是否可以分别为每一个变量赋予恰当的值,使得上述所有约束条件同时被满足。例如,一个问题中的约束条件为: x 1 = x 2 , x 2 = x 3 , x 3 = x 4 , x 1 ≠ x 4 ,这些约束条件显然是不可能同时被满足的,因此这个问题应判定为不可被满足。
现在给出一些约束满足问题,请分别对它们进行判定。
【输入格式】
输入的第 1 行包含 1 个正整数 t（t<=10） ,表示需要判定的问题个数。注意这些问题之间是相互独立的。
对于每个问题,包含若干行:第 1 行包含 1 个正整数 n（n<=100000） ,表示该问题中需要被满足的约束条件个数。
接下来 n 行,每行包括 3 个整数 i, j, e（i、j<=1000000000，0<=e<=1）,描述 1 个相等/不等的约束条件,相邻整数之间用单个空格隔开。若 e = 1 ,则该约束条件为 x i = x j ;若 e = 0 ,则该约束条件为 x i ≠ x j ;
【输出格式】
输出t 行，第 k 行输出一个字符串“YES”或者“NO”(不包含引号,字母全部大写),“YES”表示输入中的第 k 个问题判定为可以被满足,“NO”表示不可被满足。
分析：
先把e=1的用并查集合并，再判断一下e=0的是否在一个集合。i、j需要离散化。
代码：
1 #include <cstdio> 2 #include <algorithm> 3 4 int t, n, fa[200010]; 5 int tn[200010], num[200010], cnt, tot; 6 int u[100010], v[100010], w[100010]; 7 int a, b, c; 8 9 int yl(int x) 10 { 11 return fa[x] == x ? x : fa[x] = yl(fa[x]); 12 } 13 14 int low(int key) 15 { 16 int left = 1, right = cnt, mid; 17 while (left + 3 < right) 18 { 19 mid = left + right >> 1; 20 if (num[mid] == key) return mid; 21 if (num[mid] < key) left = mid; 22 else right = mid; 23 } 24 for ( ; left <= right; left++) 25 if (num[left] == key) 26 return left; 27 return -1; 28 } 29 30 int main() 31 { 32 scanf("%d", &t); 33 while (t--) 34 { 35 scanf("%d", &n); 36 tot = cnt = tn[0] = 0; 37 for (int i = 1; i <= n; i++) 38 { 39 scanf("%d%d%d", &u[i], &v[i], &w[i]); 40 tn[++tot] = u[i]; 41 tn[++tot] = v[i]; 42 } 43 std::sort(tn + 1, tn + tot + 1); 44 for (int i = 1; i <= tot; i++) 45 { 46 fa[i] = i; 47 if (tn[i - 1] != tn[i]) 48 num[++cnt] = tn[i]; 49 } 50 for (int i = 1; i <= n; i++) 51 { 52 u[i] = low(u[i]); 53 v[i] = low(v[i]); 54 } 55 for (int i = 1; i <= n; i++) 56 { 57 if (w[i] == 0) continue; 58 a = yl(u[i]); 59 b = yl(v[i]); 60 if (a != b) fa[a] = b; 61 } 62 int flag = 1; 63 for (int i = 1; i <= n; i++) 64 { 65 if (w[i] == 1) continue; 66 a = yl(u[i]); 67 b = yl(v[i]); 68 if (a == b) 69 { 70 flag = 0; 71 i = n; 72 } 73 } 74 puts(flag ? "YES" : "NO"); 75 } 76 }