P1955 [NOI2015] 程序自动分析
Tag：离散化、并查集
题目描述
在实现程序自动分析的过程中，常常需要判定一些约束条件是否能被同时满足。
考虑一个约束满足问题的简化版本：假设 \(x_1,x_2,x_3,\cdots\) 代表程序中出现的变量， 给定 \(n\) 个形如 \(x_i=x_j\) 或 \(x_i\neq x_j\) 的变量相等/不等的约束条件， 请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。 例如，一个问题中的约束条件为：\(x_1=x_2,x_2=x_3,x_3=x_4,x_4\neq x_1\)， 这些约束条件显然是不可能同时被满足的，因此这个问题应判定为不可被满足。
现在给出一些约束满足问题，请分别对它们进行判定。
数据说明：
\(1\leq n \leq 10^5,\ 1\leq i,j \leq 10^9,\ 1 \leq t \leq 10,\ e \in \{0,1\}\)
分析
首先考虑所有的 \(x = y\) 的情况，显然相等的变量之间存在传递的关系，即 \(a=b,b=c\) 同时成立时， 必然有 \(a = c\)。
这说明题目中的限制本质上是把所有的点分成若干类， 也就是说只要最后某个不等式的 \(x \neq y\)，其中 \(x,y\) 属于了同一组， 就会产生矛盾。
反过来说，如果我们事先按照所有的等式把所有变量进行分组， 在之后检查不等式的时候，如果没有发现任何一个不等式两边的变量落在同一组中， 那么就是符合题目要求的。
显然我们需要通过某种手段来维护这种分组的关系， 这一步可以通过并查集实现。
除此之外，注意到值的取值范围最大有 \(10^9\)， 显然没有办法开 \(10^9\) 大小的并查集， 但是因为最多存在 \(n\) 个式子，也就是最多存在 \(2n\) 个本质不同的变量。 因此我们可以通过离散化来处理数字，对数字编号进行并查集上的维护即可。
代码实现
struct Discretize {
vector<long long> vec;
void add(long long x) {
vec.push_back(x);
}
void init() {
std::sort(vec.begin(), vec.end());
vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
}
void init(vector<long long> v) {
vec = std::move(v);
std::sort(vec.begin(), vec.end());
vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
}
int size() { return vec.size(); }
int id(long long x) {
return std::lower_bound(vec.begin(), vec.end(), x) - vec.begin() + 1;
}
//检查是否存在元素，存在返回下标，不存在返回 0
int check_have(long long x) {
auto it = std::lower_bound(vec.begin(), vec.end(), x);
if (it == vec.end() || *it != x) return 0;
return it - vec.begin() + 1;
}
long long val(int k) {
return vec[k - 1];
}
// 查询有多少元素小于等于 x，x 可以不存在
int rank_le(long long x) {
return std::upper_bound(vec.begin(), vec.end(), x) - vec.begin();
}
};
struct DSU {
public:
vector<int> bcj;
vector<int> siz;
void Init(int n) {
bcj.resize(n + 1);
siz.resize(n + 1);
for (int i = 1; i <= n; ++i) {
bcj[i] = i;
siz[i] = 1;
}
}
int Find(int x) {
if (bcj[x] == x) return x;
return bcj[x] = Find(bcj[x]);
}
// 按秩合并
void Union(int x, int y) {
x = Find(x);
y = Find(y);
if (x == y) return;
if (siz[x] > siz[y]) swap(x, y);
bcj[x] = y;
siz[y] += siz[x];
}
};
void IHaveNoLimitation() {
int n;
cin >> n;
struct node {
int x, y, t;
};
vector<node> vec(n);
Discretize dc;
for (auto &[x, y, t]: vec) {
cin >> x >> y >> t;
dc.add(x), dc.add(y);
}
dc.init();
std::sort(vec.begin(), vec.end(), [&](auto &x, auto &y) {
return x.t > y.t;
});
DSU dsu;
dsu.Init(dc.size() + 1);
for (auto &[x, y, t]: vec) {
if (t == 1) {
dsu.Union(dc.id(x),dc.id(y));
}else{
if(dsu.Find(dc.id(x)) == dsu.Find(dc.id(y))){
cout << "NO" << endl;
return;
}
}
}
cout << "YES" << endl;
}
日志
本页面创建于 2026/3/1 11:08