洛谷 P1955 [NOI2015] 程序自动分析

【题目链接】

洛谷 P1955 [NOI2015] 程序自动分析

【题目考点】

1. 并查集

2. 离散化

【解题思路】

多组数据问题，对于每组数据，有多个$x_i=x_j$或$x_i\ne x_j$的约束条件。

所有相等的变量构成一个集合，不相等的变量在不同的集合。可以使用并查集表示集合。
该题的变量编号$i$或$j$最大可达到$10^9$，无法直接作为并查集fa数组的下标，所以需要先对所有输入的$i$与$j$进行离散化。由于每组数据输入的约束条件的数量$n\le 10^5$，每一个约束条件最多新增两个变量编号。因此在对变量编号进行离散化后，最多存在$2\ast 10^5$个元素，离散化后的数值的范围为$1\sim 2\ast 10^5$，可以作为fa数组的下标。

• 先遍历所有约束。对于$x_i=x_j$，那么可以认为$x_i$与$x_j$同属于一个集合，将$x_i$与$x_j$所在的集合合并。
• 再次遍历所有约束，对于$x_i\ne x_j$，而且$x_i$与$x_j$已属于同一集合，那么该问题中的约束条件无法都被满足，输出NO。

当看完所有约束后，如果没有输出NO，则以上约束条件可以同时满足，输出YES。

【题解代码】

#include<bits/stdc++.h>
using namespace std;
#define N 100005
struct Node
{
	int i, j, e;
};
vector<Node> op;
vector<int> t;
int fa[2*N];//不同的变量编号最多有2N个，因此并查集fa数组长度设为2N 
void init()
{
	for(int i = 1; i < 2*N; ++i)
		fa[i] = i;
}
int find(int x)
{
	return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y)
{
	fa[find(x)] = find(y);
}
void discretization()
{
	sort(t.begin(), t.end());
	t.erase(unique(t.begin(), t.end()), t.end());
	for(Node &p : op)
	{
		p.i = upper_bound(t.begin(), t.end(), p.i)-t.begin();//离散化后，变量编号范围为1~2*10^5 
		p.j = upper_bound(t.begin(), t.end(), p.j)-t.begin();
	}
}
bool isMatch()//是否可以满足给定的所有约束 
{
	for(Node p : op) if(p.e == 0 && find(p.i) == find(p.j))
		return false;
	return true;
}
int main()
{
	int tn, n, i, j, e;
	cin >> tn;
	while(tn--)
	{
		op.clear();
		t.clear();
		init();
		cin >> n;
		for(int k = 1; k <= n; ++k)
		{
			cin >> i >> j >> e;
			op.push_back(Node{i, j, e});
			t.push_back(i);
			t.push_back(j);
		}
		discretization();
		for(Node p : op) if(p.e == 1)//如果是xi=xj 
			merge(p.i, p.j);
		cout << (isMatch() ? "YES" : "NO") << '\n';
	}
	return 0;
}