迷途漫漫，终有一归。
程序自动分析
时间限制: 2 Sec 内存限制: 256 MB
[提交] [状态]
题目描述
在实现程序自动分析的过程中,常常需要判定一些约束条件是否能被同时满足。
考虑一个约束满足问题的简化版本：假设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”表示不可被满足。
样例输入 Copy
2
2
1 2 1
1 2 0
2
1 2 1
2 1 1
样例输出 Copy
NO
YES
提示
在第一个问题中，约束条件为：x1=x2,x1≠x2。这两个约束条件互相矛盾，因此不可被同时满足。
在第二个问题中，约束条件为：x1=x2,x2=x1。这两个约束条件是等价的，可以被同时满足。
1≤n≤1000000
1≤i,j≤1000000000
思路：
并查集判冲突很常见的，但这题的数据范围着实虾仁。
我们可以对数据进行离散化，离散化通常有两种
（1）保序：排序 判重 二分
（2）不需要排序：map || hash
然后我们可以先考虑相等约束，在这个过程中是没有矛盾的。然后我们再考虑不等条件 若x,y在一种集合里 说明存在矛盾
代码： （离散化属实难写）
#include<bits/stdc++.h> using namespace std; typedef unsigned long long ull; typedef long long ll; typedef pair<int, int> PII; #define I_int ll inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } char F[200]; inline void out(I_int x) { if (x == 0) return (void) (putchar('0')); I_int tmp = x > 0 ? x : -x; if (x < 0) putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0) putchar(F[--cnt]); //cout<<" "; } const int maxn=2e6+7; int n,m,root[maxn]; unordered_map<int,int>mp;///hash struct node{ int x,y,op; }a[maxn];///存储输入 int push(int x){ if(!mp.count(x)) mp[x]=++n; return mp[x]; } int Find(int x){ if(x!=root[x]) root[x]=Find(root[x]); return root[x]; } void Union(int x,int y){ x=Find(x),y=Find(y); if(x!=y) root[x]=y; } bool query(int x,int y){ x=Find(x),y=Find(y); if(x==y) return 1; return 0; } void AC(){ int t;t=read(); while(t--){ m=read();n=0; mp.clear();///一定要清零！ for(int i=1;i<=m;i++){ int x,y,op; x=read();y=read();op=read(); a[i].x=push(x);a[i].y=push(y);a[i].op=op; } for(int i=0;i<=n;i++) root[i]=i;///并查集初始化 for(int i=1;i<=m;i++) if(a[i].op) Union(a[i].x,a[i].y); bool flag=1; for(int i=1;i<=m;i++) if(!a[i].op){ if(query(a[i].x,a[i].y)){ flag=0; break; } } if(flag) puts("YES"); else puts("NO"); } } int main(){ AC(); return 0; }
并查集判冲突的还有 How Many Answers Are Wrong HDU - 3038
代码：
#include<bits/stdc++.h> using namespace std; const int maxn=500086; int root[maxn],dep[maxn]; int n,m; int x,y,z; void init(int n){ for(int i=0;i<=n;i++){ dep[i]=0; root[i]=i; } } int Find(int x){ if(root[x]!=x) { int fx=root[x]; root[x]=Find(root[x]); dep[x]+=dep[fx]; } return root[x]; } void Union(int fx,int fy,int z){ root[fx]=fy; dep[fx]=dep[y]-dep[x]+z; } int main(){ while(~scanf("%d%d",&n,&m)){ init(n); int ans=0; //cout<<m<<" "; for(int i=1;i<=m;i++){ cin>>x>>y>>z; x-=1; int fx=Find(x),fy=Find(y); if(fx==fy){ if(dep[x]-dep[y]!=z) ans++; } else{ //Union(fx,fy,z); root[fx]=fy; dep[fx]=dep[y]-dep[x]+z; } } cout<<ans<<endl; } return 0; }
