[NOI 2015] 程序自动分析

知识点

并查集、离散化、约束满足

解题思路

读入一个问题的所有约束，收集变量编号并排序去重，离散化为连续下标。先处理所有等式，用并查集合并；再检查每个不等式的两端是否已在同一集合，若是则无解，否则有解。每个问题独立初始化。

正确性说明

等式的传递闭包由并查集恰好表示。若某不等式两端在同一闭包类中必矛盾；若不存在这样的不等式，给每个闭包类一个互不相同的值即可同时满足所有约束，故判定充分必要。

易错点

不能在后续等式尚未读完时就宣布不等式成立；自我不等立即矛盾；重复等式合法；变量编号可达十亿，不按原编号开数组。

复杂度

每个问题时间O(n log n+nα(n))，空间O(n)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
struct DSU{vector<int>p,s;DSU(int n):p(n),s(n,1){iota(p.begin(),p.end(),0);}int f(int x){while(x!=p[x]){p[x]=p[p[x]];x=p[x];}return x;}void join(int a,int b){a=f(a);b=f(b);if(a==b)return;if(s[a]<s[b])swap(a,b);p[b]=a;s[a]+=s[b];}};
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t;cin>>t;while(t--){int n;cin>>n;vector<array<int,3>>a(n);vector<int>v;for(auto&z:a){cin>>z[0]>>z[1]>>z[2];v.push_back(z[0]);v.push_back(z[1]);}sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());for(auto&z:a){z[0]=lower_bound(v.begin(),v.end(),z[0])-v.begin();z[1]=lower_bound(v.begin(),v.end(),z[1])-v.begin();}DSU d(v.size());for(auto z:a)if(z[2])d.join(z[0],z[1]);bool ok=true;for(auto z:a)if(!z[2]&&d.f(z[0])==d.f(z[1]))ok=false;cout<<(ok?"YES":"NO")<<'\n';}}