题目描述
在实现程序自动分析的过程中,常常需要判定一些约束条件是否能被同时满足。
考虑一个约束满足问题的简化版本:假设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”表示不可被满足。
数据范围
1≤n≤1000000
1≤i,j≤1000000000
样例
#include<bits/stdc++.h>
using namespace std;
int OPQ,f[400000+10],me[400000+10],u[400000+10],v[400000+10],z;
// f[] 记录当前下标(对应的数)的父亲(祖宗)的下标;
// me[] 记录当前下标对应的数;
// u[] 记录不同两数之一;
// v[] 记录不同两数之另一;
// z 记录不同两数有几组;
int n,p;
int fa(int a){ // 找祖宗的下标;
if(f[a]!=a) f[a]=fa(f[a]);
return f[a];
}
int find(int a){ // 找该数的下标;
int k=a%200003;
for(;me[k]!=a&&me[k];) k++;
me[k]=a;
return k;
}
void jia(int a,int b){ // 并查集;
a=fa(a);
b=fa(b);
if(a==b) return;
f[b]=a;
}
int main(){
scanf("%d",&OPQ);
while(OPQ--){
p=1;
z=0;
scanf("%d",&n);
for(int i=1;i<400001;i++){
f[i]=i;
me[i]=0;
} // 重置;
while(n--&&p){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(c) jia(find(a),find(b));
else{
u[++z]=find(a);
v[z]=find(b);
}
}
while(z){
if(fa(u[z])==fa(v[z])){ // 是否同祖宗;
puts("NO");
p=0;
break;
}
z--;
}
if(p) puts("YES");
}
return 0;
}
先将那些题目给出相等的数并查集,不相等的暂时储存。
再把不相等的逐条判断{
1.在同一集合内 -> false -> break;
2.不在同一集合内 -> continue;
}
ps : 使用并查集时注意,因范围过大,需要用哈希表储存。
1s 就可以过的线性时间,3s就更不虚了。
int k=a%200003;
for(;me[k]!=a&&me[k];) k++;是什么意思啊
这个离散化很容易冲突啊
离散化这么写会不会超时呀
https://www.acwing.com/problem/content/submission/code_detail/5192834/
能帮忙看下,我这个代码为什么过不去吗?
find函数中少了行代码 me[k]=a;
感谢提出问题,已改正。
可以问下find函数不处理冲突的话是怎么A的。。,me数组在代码中根本没有赋值
1
10
1 2 1
2 3 1
3 5 1
5 10 1
10 100 1
10000 100 1
1 9999 0
3 2 1
10000 1 0
1 200004 1
以上数据的话200004和1哈希冲突mod200003,但是发现输出的k是同一个
感谢你的提问。判重的话,(如果赋值了的话)find函数中“me[k]!=a”已经处理了。因为me[k]中若已经有数了,就会对新数a与之比较,若不同,则往后找属于a的位置。
赋值是我疏忽了,可能因为测试点比较容易,没有冲突,才能A。
不过已改正。