BZOJ题目传送门 洛谷题目传送门
应该挺好想的并查集。
先离散化一波，然后把条件排个序，把相等的排前面。扫一遍过去，先把相等的都连好，如果有不相等的但是在同一个块中就退出判 NO N O ，否则就是 YES Y E S 。
没清零+数组开小RE4发。。。
代码：
#include<cctype> #include<cstdio> #include<cstring> #include<algorithm> #define N 100005 #define F inline using namespace std; struct node{ int x,y; bool f; }a[N]; int t,n,m,fa[N<<1],b[N<<1]; F char readc(){ static char buf[100000],*l=buf,*r=buf; if (l==r) r=(l=buf)+fread(buf,1,100000,stdin); return l==r?EOF:*l++; } F int _read(){ int x=0; char ch=readc(); while (!isdigit(ch)) ch=readc(); while (isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=readc(); return x; } F bool cmp(node a,node b){ return a.f>b.f; } F int findfa(int x){ return x==fa[x]?x:fa[x]=findfa(fa[x]); } int main(){ for (t=_read();t;t--){ n=_read(),m=0; bool f=false; for (int i=1;i<=n;i++){ a[i].x=b[++m]=_read(); a[i].y=b[++m]=_read(); a[i].f=_read(); } sort(b+1,b+m+1),m=unique(b+1,b+m+1)-b-1; for (int i=1;i<=m;i++) fa[i]=i; sort(a+1,a+n+1,cmp); for (int i=1,x,y;i<=n;i++){ x=lower_bound(b+1,b+m+1,a[i].x)-b; y=lower_bound(b+1,b+m+1,a[i].y)-b; int fx=findfa(x),fy=findfa(y); if (a[i].f&&fx!=fy) fa[fx]=fy; if ((!a[i].f)&&fx==fy){ puts("NO"),f=true; break; } } if (!f) puts("YES"); } }