约束条件

题目描述

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

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

输入格式

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

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

第一行包含一个正整数 n，表示该问题中需要被满足的约束条件个数。接下来 n行，每行包括三个整数x,y,e ，描述一个相等/不等的约束条件，相邻整数之间用单个空格隔开。若e=1 ，则该约束条件为x1=x2 。若 e=0，则该约束条件为x1<>x2 。

输出格式

输出包括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

数据范围与提示

对于100%  的数据，1<=t<=10，1<=n<=1e6，e是0或1，1<=i,j<=1e9。

分析：并查集经典题

先合并所有e=1的条件，再判断e=0的条件是否合法。

1e6个条件不多，但条件中的i，j很大，达1e9，每个条件2个数，所以最多只有2e6个不同的数，所以可以做个离散化。

参考代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define re register 
 4 #define LL long long
 5 const int MAXN = 1e6+10;
 6 
 7 int T,fa[2*MAXN];
 8  
 9 inline int find(int x){
10     if(fa[x]==x) return x;
11     return fa[x]=find(fa[x]);  
12 }
13  
14 struct nod1{int x,y,e;}edges[MAXN]; 
15 inline int cmp1(nod1 a,nod1 b) {
16     if(a.e==b.e) return a.x<b.x;
17     return a.e>b.e;
18 } 
19 // 先处理相等的情况，再处理不等的情况 
20 
21 int main() {     
22     cin>>T;
23     while(T--){
24         
25         map<int,int>M2idx;
26         int n;cin>>n;        
27         for (re int i=1;i<=n;i++) {
28             int x,y,e;
29             cin>>x>>y>>e;
30             M2idx[x]=1;M2idx[y]=1; 
31             edges[i].x=x;edges[i].y=y;edges[i].e=e;    
32         }  
33                 
34         //离散化 
35         int idx=0 ;       
36         for(auto it:M2idx){
37            M2idx[it.first]=++idx; 
38            fa[idx]=idx; 
39         }
40         sort(edges+1,edges+1+n,cmp1);
41         
42         string res="YES";
43         for (re int i=1;i<=n;i++) { 
44                           
45            int x=M2idx[edges[i].x],y=M2idx[edges[i].y],e=edges[i].e;
46            
47            int fax=find(x);int fay=find(y);
48            
49            if(e==1){
50                 if (fax!=fay) {fa[fax]=fay;}
51            }
52            else if(fax==fay){
53                   res="NO";
54                   break; 
55            }         
56         }
57         cout<<res<<endl;
58     }
59         
60     return 0;
61 }