题面：BZOJ4195 Luogu1955 由于这个区间范围挺大的，但是点不多，所以考虑离散化 离散化之后呢就直接并查集就好了 等于的直接合并，不等于的判断是否在同一连通块里 要注意的是要所有合并完之后才能判断不等于的情况 离散化用的std::map
#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <iostream> #include <cstdlib> #include <map> #include <ctime> #include <queue> #include <climits> using namespace std; map<int,int>mp; int fa[200001]; struct ppap{int x,y,v;}a[100001]; inline bool cmp(ppap a,ppap b){return a.v>b.v;} inline int getfather(int v){return fa[v]==v?v:fa[v]=getfather(fa[v]);} int main() { int T,n,m;scanf("%d",&T); while(T--){ mp.clear();m=0; scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].v); if(!mp[a[i].x])mp[a[i].x]=++m; if(!mp[a[i].y])mp[a[i].y]=++m; a[i].x=mp[a[i].x];a[i].y=mp[a[i].y]; } sort(a+1,a+n+1,cmp); for(int i=1;i<=2*n;i++)fa[i]=i; bool flag=1; for(int i=1;i<=n;i++){ int fx=getfather(a[i].x),fy=getfather(a[i].y); if(a[i].v)fa[fx]=fy; else if(fx==fy){flag=0;break;} } if(flag)puts("YES"); else puts("NO"); } return 0; }