[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;
}