题目来源：洛谷

题目描述

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

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

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

输入输出格式

 

输入格式：

 

从文件prog.in中读入数据。

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

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

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

 

输出格式：

 

输出到文件 prog.out 中。

输出文件包括t行。

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

在第一个问题中，约束条件为：x1=x2,x1≠x2。这两个约束条件互相矛盾，因此不可被同时满足。

在第二个问题中，约束条件为：x1=x2,x1=x2。这两个约束条件是等价的，可以被同时满足。

【样例说明2】

在第一个问题中，约束条件有三个：x1=x2,x2=x3,x3=x1。只需赋值使得x1=x1=x1，即可同时满足所有的约束条件。

在第二个问题中，约束条件有四个：x1=x2,x2=x3,x3=x4,x4≠x1。由前三个约束条件可以推出x1=x2=x3=x4，然而最后一个约束条件却要求x1≠x4，因此不可被满足。

【数据范围】

【时限2s，内存512M】

 

解析：

这道题是一个很明显的使用并查集维护具有传递性的信息的思路。

思路：

我们可以把它看作一个图，每个x是其上的一个点，每对xi，xj之间的关系是一条无向边。

由于"="具有传递性，也就是说，当x1=x2，x2=x3时，有x1=x3。因此，我们可以通过维护并查集，使所有相等的x处于同一集合。

然后在对e=0的情况做判断，也就是“≠”，如果查询的某对xi，xj属于同一个集合，那么当前问题就是不可满足的。

具体而言，我们把e=1的关系分到一组，e=0的关系分到另一组，先用并查集维护e=1时的情况，再对e=0时的情况进行查询，如果有两个点属于同一个集合，那么显然不成立。

 

然而这题的毒瘤数据范围在10^9的数量级，我们要在这样一个范围上维护并查集，会TLE掉。

 

默默点开标签，看到离散化，嘿嘿。

离散化又是什么？通俗的讲，离散化就是把无穷大（对计算机而言）集合中的若干个元素映射为有限集合以便于统计的方法。

在这道题目中，我们无须知道具体的xi，xj的值，只需要知道这些数之间的关系，所以我们可以使用离散化。

离散化的模板如下：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #include<cstring>
 5 #include<ctime>
 6 #include<cstdlib>
 7 #include<algorithm>
 8 #include<queue>
 9 #include<set>
10 #include<map>
11 #define N 100010
12 using namespace std;
13 int a[N],b[N];
14 int main()
15 {
16     int n;
17     cin>>n;
18     int cnt=0;
19     for(int i=1;i<=n;i++){
20         scanf("%d",&a[i]);
21         b[++cnt]=a[i];
22     }
23     sort(b+1,b+n+1);
24     int len=unique(b+1,b+n+1)-(b+1);
25     cout<<len<<endl;
26     for(int i=1;i<=n;i++)
27     {
28         a[i]=lower_bound(b+1,b+len+1,a[i])-b;
29     }
30     for(int i=1;i<=n;i++) cout<<a[i]<<' ';
31     return 0;
32 }

注意本题中有两组亟需离散化的量，我们可以照样把他们放到一个暂存数组中进行离散化，因为他们的相对位置是不变的。

参考代码：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #include<cstring>
 5 #include<ctime>
 6 #include<cstdlib>
 7 #include<algorithm>
 8 #include<queue>
 9 #include<set>
10 #include<map>
11 #define N 100010
12 using namespace std;
13 int b[N*2],fa[N];
14 struct node{
15     int x,y,e;
16 }a[N];
17 bool cmp(node a,node b){
18     return a.e>b.e;
19 }
20 int get(int x)
21 {
22     if(fa[x]==x) return x;
23     return fa[x]=get(fa[x]);
24 }
25 void merge(int x,int y)
26 {
27     fa[x]=y;
28 }
29 int main()
30 {
31     int n;
32     cin>>n;
33     while(n--)
34     {
35         memset(a,0,sizeof(a));
36         memset(b,0,sizeof(b));
37         memset(fa,0,sizeof(fa));
38         int t,k=0,cnt=0;
39         scanf("%d",&t);
40         
41         for(int i=1;i<=t;i++)
42         {
43             scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].e);
44             b[++cnt]=a[i].x;b[++cnt]=a[i].y;
45         }
46         //离散化 
47         sort(b+1,b+cnt+1);
48         int len=unique(b+1,b+cnt+1)-b;
49         for(int i=1;i<=t;i++){
50             a[i].x=lower_bound(b+1,b+len+1,a[i].x)-b;
51             a[i].y=lower_bound(b+1,b+len+1,a[i].y)-b;
52         }
53         for(int i=1;i<=len;i++) fa[i]=i;
54         sort(a+1,a+t+1,cmp);
55         for(int i=1;i<=t;i++)
56         {
57             if(a[i].e){
58                 int x=get(a[i].x);
59                 int y=get(a[i].y);
60                 if(x!=y) merge(x,y);
61             }
62             else{
63                 int x=get(a[i].x);
64                 int y=get(a[i].y);
65                 //printf("%d follows %d,%d follows %d\n",a[i].x,x,a[i].y,y);
66                 if(x==y){
67                     k=1;
68                     break;
69                 }
70             }
71         }
72         if(k) cout<<"NO"<<endl;
73         else cout<<"YES"<<endl;
74     }
75     return 0;
76 }