题目描述

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

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

现在给出一些约束满足问题，请分别对它们进行判定。

原题链接

Solve

简单点说，就是用并查集莽就完了。

用每个x做节点，然后，先检查等于的情况，将其中的x合并到一个集合中，最后检查不等于的情况，如果在一个集合内就是“NO”，如果都不在一个集合内就是“YES”。

但是有趣的是x的范围是10e9的，这要是做数组下标，那么一大堆MLE和CE都等着你，当场毙命。

于是我们理性的分析分析，虽然范围大，但是每次最多有2*n个数字不同，所以你懂我意思吧。

离散化。

数据问题解决了，面前就是一马平川，莽！注意是多组数据，记得重置。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 2100000
using namespace std;
int t,n;
int fa[N];
int num[N],cnt,len1,len2,op,b[N];
int x,y,z;
bool flag;
struct note{
	int u,v,w;
}d[N];
int find(int s){
	if(fa[s]!=s) fa[s]=find(fa[s]);
	return fa[s];
}
int query(int s){
	return lower_bound(b+1,b+op+1,s)-b;
}
int main()
{
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		cnt=0;op=0;len1=0;len2=n+1;flag=false;
		for(int i=1;i<=2*n;i++) fa[i]=i;
		for(int i=1;i<=n;i++){
			scanf("%d%d%d",&x,&y,&z);
			num[++cnt]=x; 
			num[++cnt]=y;
			if(z) d[++len1].u=x,d[len1].v=y,d[len1].w=z;
			else d[--len2].u=x,d[len2].v=y,d[len2].w=z;
            //两个“指针”，两边放。
		}
		sort(num+1,num+1+cnt);
		for(int i=1;i<=cnt;i++){
			if(i==1||num[i]!=num[i-1]) b[++op]=num[i];
		}
		for(int i=1;i<=n;i++)d[i].u=query(d[i].u),d[i].v=query(d[i].v); 
		for(int i=1;i<=n;i++){
			int e=find(d[i].u),r=find(d[i].v);
			if(d[i].w){
				if(e!=r) fa[r]=e;
			}
			else{
				if(e==r){flag=true;printf("NO\n");break;}
			}
		}
		if(!flag) printf("YES\n");
	}
	return 0;
}

后言

小心用map，反正我的死了。