题目描述
在实现程序自动分析的过程中,常常需要判定一些约束条件是否能被同时满足。
考虑一个约束满足问题的简化版本:假设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 }
标签:约束条件,int,edges,x2,YES,x1 From: https://www.cnblogs.com/flatte/p/17589599.html