原题链接：https://www.luogu.org/problem/show?pid=1955
夏令营的模拟考试题，今天才发现是NOI原题，没想到15年也有这样裸的题。。。
离散化一下，这样就能用并查集来处理问题，然后逐个判断，相等的就将其合并，不相等就判断是否真的不相等，如果已知两数相等，那么就能确定不可被满足。
除了离散化有点玄学之外，其他的倒是挺正常的并查集。。。
#include<cstdio> #include<algorithm> using namespace std; int u[100005],v[100005],e[100005],f[200005],n,tmp[200005],t; int find(int x) { if(x==f[x]) return x; return f[x]=find(f[x]); } void solve() { scanf("%d",&n); for(int i=1;i<=n*2;++i) f[i]=i; for(int i=1;i<=n;++i) { scanf("%d%d%d",&u[i],&v[i],&e[i]); tmp[i*2-1]=u[i],tmp[i*2]=v[i]; } sort(tmp+1,tmp+1+n*2); for(int i=1;i<=n;++i) { u[i]=lower_bound(tmp+1,tmp+1+n*2,u[i])-tmp; v[i]=lower_bound(tmp+1,tmp+1+n*2,v[i])-tmp; if(e[i]&&find(u[i])!=find(v[i])) f[find(u[i])]=v[i]; } for(int i=1;i<=n;++i) { if(e[i]) continue; if(find(u[i])==find(v[i])) { printf("NO\n"); return; } } printf("YES\n"); } int main() { scanf("%d", &t); while(t--) solve(); return 0; }
原文：http://www.cnblogs.com/zeroform/p/7562952.html