「LOJ 2129」「NOI2015」程序自动分析

发表于

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

考虑一个约束满足问题的简化版本：假设 x1,x2,x3,…x_1, x_2, x_3,\ldots 代表程序中出现的变量，给定 nn 个形如 xi=xjx_i=x_j 或 xi≠xjx_i \neq x_j 的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。现在给出一些约束满足问题，请分别对它们进行判定。

Constraints

T≤10T \leq 10 ， n≤106n \leq 10^6

Solution

直接离散化后使用并查集维护即可。先处理相等关系，再处理不相等关系。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<cstdio>
#include<algorithm> 
#include<cstring>
#define LL long long
using namespace std;
const int N=1e6+5;
int T,n,cnt,p,q;
int x[N],y[N],e[N];
int a[N*2],f[N*2];
bool ans;
int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
int find(int t){return f[t]==t?t:f[t]=find(f[t]);}
int main()
{
	T=read();
	while(T--)
	{
		n=read();ans=true;
		for(int i=1;i<=n;i++)
		{
			x[i]=read();y[i]=read();e[i]=read();
			a[++cnt]=x[i];a[++cnt]=y[i];
		}
		sort(a+1,a+cnt+1);
		cnt=unique(a+1,a+cnt+1)-a-1;
		for(int i=1;i<=n;i++)
			x[i]=lower_bound(a+1,a+cnt+1,x[i])-a,
			y[i]=lower_bound(a+1,a+cnt+1,y[i])-a;
		for(int i=1;i<=cnt*2;i++)f[i]=i;
		for(int i=1;i<=n;i++)
			if(e[i])
			{
				p=find(x[i]);q=find(y[i]);
				if(p!=q)f[p]=q;
			}
		for(int i=1;i<=n;i++)
			if(!e[i])
			{
				p=find(x[i]);q=find(y[i]);
				if(p==q)ans=false;
			}
		if(!ans)printf("NO\n");
		else printf("YES\n");
	}
	return 0;
}