题意:暂且并没有链接方法:并查集+离散化解析:国赛这道普及组难度的题我都不好意思写题解，这道题的题意非常明了，一眼题..其实就是把所有的要求sort一下，把令xi=xj的条件放在前面，，令xi!=xj的条件放到后面就行了。然后我们对于n个询问，先把所有的i,j离散化，这里我偷懒用了map然后只需要将所有xi=xj的部分加到并查集里。xi!=xj的部分看一下二者的祖先相不相同就行了，不相同就判断下一个，相同输出no；代码:这道题贴代码真是不好意思- -; int tot; int t; int n; int fa[N<<1]; map<int,int>m; struct node {int x,y,z; }a[N]; int find(int x) {if(fa[x]==x)return x;else fa[x]=find(fa[x]);return fa[x]; } int cmp(node a,node b){return a.z>b.z;} int main() {scanf(“%d”,&t);while(t–){tot=0;m.clear();scanf(“%d”,&n);for(int i=1;i<=n;i++){scanf(“%d%d%d”,&a[i].x,&a[i].y,&a[i].z);}for(int i=1;i<=n;i++){if(!m[a[i].x])m[a[i].x]=++tot;if(!m[a[i].y])m[a[i].y]=++tot;}for(int i=1;i<=tot;i++)fa[i]=i;int flag=0;sort(a+1,a+n+1,cmp);for(int i=1;i<=n;i++){int x=m[a[i].x],y=m[a[i].y];int z=a[i].z;if(z==1){int fx=find(x),fy=find(y);if(fx!=fy){fa[fx]=fy;}}else{int fx=find(x),fy=find(y);if(fx==fy){printf(“NO\n”);flag=1;break;}}}if(!flag)printf(“YES\n”);} }
呼唤你前往另一个地方，过上另一种生活。
