【题解】Luogu P1955 BZOJ P4195 【[NOI2015]程序自动分析】

这道题就是被誉为NOI最水的一题,可用离散化加并查集解决,但是我不会写很厉害的离散化,所以我就随便模了一个数,顺手就A了23333。

先满足所有“相等”类型的约束条件。显然,将每个变量看作无向图的结点,那么“相等”类型的条件就是一条边,那么两个变量相等当且仅当它们连通。所以我们把每个变量分成若干个集合,每个集合都对应无向图中的联通块。

方法有两种:

①建立无向图,深搜,划分出联通块,不好写,,,放弃。

②用并查集维护,起初各自变量自成一个集合,对于每个“相等“的约束条件,合并它们所在的集合。最后扫描所有”不等“条件,若存在一条不等条件,它约束的两个变量处于同一个集合内,则不可能满足。

#include<cstdio>

typedef long long int64;

const int MAXN = 1000001;
int64 fa[MAXN],I[MAXN],J[MAXN];

int get(int x){
	if(x == fa[x]){
		return x;
	}
	return fa[x] = get(fa[x]);
}

int merge(int x,int y){
	fa[get(x)] = get(y);
}

int main(){
	int T;
	scanf("%d",&T);
	
	while(T--){
		int64 n;
		scanf("%lld",&n);
		
		for(int i = 1;i <= MAXN;i++){
			fa[i] = i;
		}
		
		int64 i,j,e,cnt = 0;
		bool running = true;
		for(int gg = 0;gg < n;gg++){
			scanf("%lld %lld %lld",&i,&j,&e);
			
			i %= 521475;
			j %= 521475; 
			
			if(e == 1){
				merge(i,j);
			}else{
				I[++cnt] = i;
				J[cnt] = j;
			}
		}
		
		for(int gg = 1;gg <= cnt;gg++){
			if(get(I[gg]) == get(J[gg])){
				running = false;
			}
		}
		
		if(!running){
			printf("NO\n");
		}else{
			printf("YES\n");
		}
	}
	
	return 0;
}