本文共 3103 字，大约阅读时间需要 10 分钟。

题目描述

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

考虑一个约束满足问题的简化版本：假设$x_1$,$x_2$,$x_3$,…代表程序中出现的变量，给定$n$个形如$x_i=x_j$或$x_i\ne x_j$的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。例如，一个问题中的约束条件为：$x_1=x_2$，$x_2=x_3$，$x_3=x_4$，$x_1\ne x_4$，这些约束条件显然是不可能同时被满足的，因此这个问题应判定为不可被满足。
现在给出一些约束满足问题，请分别对它们进行判定。

输入格式

输入文件的第$1$行包含$1$个正整数$t$，表示需要判定的问题个数。注意这些问题之间是相互独立的。

对于每个问题，包含若干行：
第$1$行包含$1$个正整数$n$，表示该问题中需要被满足的约束条件个数。
接下来$n$行，每行包括$3$个整数$i$,$j$,$e$，描述$1$个相等/不等的约束条件，相邻整数之间用单个空格隔开。若$e=1$，则该约束条件为$x_i=x_j$；若$e=0$，则该约束条件为$x_i\ne x_j$。

输出格式

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

样例

输入

221 2 11 2 021 2 12 1 1

输出

NOYES

数据范围与提示

对于所有的数据，$1\le t\le 10$，$1\le n\le 10^6$，$1\le i,j\le 10^9$。

分析

显然，这是一道并查集的题。
因为$i,j$两数有可能很大，$fa$数组很可能装不下，而$1\le n\le 10^6$，$fa$数组是可以装下的，所以考虑离散化。
做法：循环一遍，将$i=j$的情况存在$fa$数组中。再循环一遍，考虑$i\ne j$的情况，若$fa$数组中$i$和$j$的父亲相等了，就说明矛盾了。
时间复杂度：$O(Tnlo{g}_2(n))$。

代码

#include <cstdio>#include <algorithm>#include <cmath>#include <climits>#include <cstring>using namespace std;const int MAXN = 1e6 + 5;int fa[MAXN], Rank[MAXN], cnt, X[MAXN], Y[MAXN], Z[MAXN], lsh[MAXN << 1], Size, num[MAXN][2];bool flag;void read(int &x) {   //读优    int f = 1;    x = 0;    char c = getchar();    while(c < '0' || c > '9') {           if(c == '-') f = -1;        c = getchar();    }    while(c >= '0' && c <= '9') {           x = x * 10 + (c - '0');        c = getchar();    }    x *= f;}void Make_Set(int n) {   //初始化	for(int i = 1; i <= n; i ++) {   		fa[i] = i;		Rank[i] = 0;	}	return;}int Find_Set(int x) {   //找父亲（路径压缩）	if(fa[x] != x) {   		return fa[x] = Find_Set(fa[x]); 	}	return fa[x];}void Union_Set(int x, int y) {   //按秩合并	int i = Find_Set(x), j = Find_Set(y);	if(i == j) return;	if(Rank[i] < Rank[j]) fa[i] = j;	else {   		fa[j] = i;		if(Rank[i] == Rank[j]) Rank[i] ++;	}	return;}bool Union_Sets(int x, int y) {   //判断是否矛盾	int i = Find_Set(x), j = Find_Set(y);	if(i == j) return 1;	return 0;}int main() {   	int T, n; 	read(T);	while(T --) {   		memset(lsh, 0, sizeof(lsh));		cnt = 0; flag = 1;		read(n);		for(int i = 1; i <= n; i ++) {   			read(X[i]); read(Y[i]); read(Z[i]);			lsh[++ cnt] = X[i];			lsh[++ cnt] = Y[i];		}		sort(lsh + 1, lsh + 1 + cnt);		Size = unique(lsh + 1, lsh + 1 + cnt) - lsh - 1;		Make_Set(Size);		for(int i = 1; i <= n; i ++) {   			num[i][0] = lower_bound(lsh + 1, lsh + 1 + Size, X[i]) - lsh;//离散化			num[i][1] = lower_bound(lsh + 1, lsh + 1 + Size, Y[i]) - lsh;		}		for(int i = 1; i <= n; i ++) {   			if(Z[i] == 1) Union_Set(num[i][0], num[i][1]);		}		for(int i = 1; i <= n; i ++) {   			if(Z[i] == 0 && Union_Sets(num[i][0], num[i][1])) {   				flag = 0;				printf("NO\n");				break;			}		}		if(flag) {   			printf("YES\n");		}	}	return 0;}