[UOJ#127][BZOJ4195][NOI2015]程序自动分析

试题描述

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

考虑一个约束满足问题的简化版本：假设x1,x2,x3,…代表程序中出现的变量，给定n个形如xi=xj或xi≠xj的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。例如，一个问题中的约束条件为：x1=x2，x2=x3，x3=x4，x1≠x4，这些约束条件显然是不可能同时被满足的，因此这个问题应判定为不可被满足。

现在给出一些约束满足问题，请分别对它们进行判定。

输入

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

对于每个问题，包含若干行：

第1行包含1个正整数n，表示该问题中需要被满足的约束条件个数。

接下来n行，每行包括3个整数i,j,e，描述1个相等/不等的约束条件，相邻整数之间用单个空格隔开。若e=1，则该约束条件为xi=xj；若e=0，则该约束条件为xi≠xj。

输出

输出文件包括t行。

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

输入示例

输出示例

NO
YES

数据规模及约定

1≤n≤1000000

1≤i,j≤1000000000

题解

离散化后，用个并查集，对于相等的两个变量把它们放在同一个连通块里，然后判断所有不等的条件中的两个元素是否在同一个连通块，在就输出 NO，否则输出 YES。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;

const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *Tail;
inline char Getchar() {
	if(Head == Tail) {
		int l = fread(buffer, 1, BufferSize, stdin);
		Tail = (Head = buffer) + l;
	}
	return *Head++;
}
int read() {
	int x = 0, f = 1; char c = Getchar();
	while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); }
	while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); }
	return x * f;
}

#define maxn 100010

int fa[maxn<<1], cnt[2], num[maxn<<1], cntn;
struct Que {
	int x, y;
	Que() {}
	Que(int _, int __): x(_), y(__) {}
} con[2][maxn];

int findset(int x) { return x == fa[x] ? x : fa[x] = findset(fa[x]); }

int main() {
	int T = read();
	while(T--) {
		int n = read();
		cnt[0] = cnt[1] = cntn = 0;
		for(int i = 1; i <= n; i++) {
			int x = read(), y = read(), tp = read();
			num[++cntn] = x; num[++cntn] = y;
			con[tp][++cnt[tp]] = Que(x, y);
		}
		sort(num + 1, num + cntn + 1);
		cntn = unique(num + 1, num + cntn + 1) - num - 1;
		for(int i = 1; i <= cntn; i++) fa[i] = i;
		for(int tp = 0; tp < 2; tp++)
			for(int i = 1; i <= cnt[tp]; i++)
				con[tp][i].x = lower_bound(num + 1, num + cntn + 1, con[tp][i].x) - num,
				con[tp][i].y = lower_bound(num + 1, num + cntn + 1, con[tp][i].y) - num;
		for(int i = 1; i <= cnt[1]; i++) {
			int u = findset(con[1][i].x), v = findset(con[1][i].y);
			if(u != v) fa[v] = u;
		}
		bool ok = 1;
		for(int i = 1; i <= cnt[0]; i++) {
			int u = findset(con[0][i].x), v = findset(con[0][i].y);
			if(u == v){ ok = 0; break; }
		}
		puts(ok ? "YES" : "NO");
	}
	
	return 0;
}