正題

評測記錄:https://www.luogu.org/recordnew/lists?uid=52918&pid=P1955

---

題目大意

給出若干個關系，xi≠xj???or???xi=xjxi≠xjorxi=xj，然后求是否全部都滿足。

---

解題思路

首先由于數據較大，所以我們先離散化，然后用并查集。先處理所有等于的關系，然后不等于的再判斷。

---

code

#include<cstdio> #include<algorithm> #define N 1000010 using namespace std; struct node{int x,y,t; }a[N]; int n,uniq[2*N],f[2*N],t; bool cmp(node x,node y) {return x.t>y.t; } int find(int x) {if(f[x]!=x) return f[x]=find(f[x]);return x; } int main() {scanf("%d",&t);for(int ti=1;ti<=t;ti++){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].t);uniq[i]=a[i].x;uniq[i+n]=a[i].y;}//以上為去重stable_sort(uniq+1,uniq+1+2*n);int m=unique(uniq+1,uniq+1+2*n)-(uniq+1);//以上為離散化for(int i=1;i<=m;i++) f[i]=i;//初始化并查集for(int i=1;i<=n;i++){a[i].x=lower_bound(uniq+1,uniq+1+m,a[i].x)-(uniq+1),a[i].y=lower_bound(uniq+1,uniq+1+m,a[i].y)-(uniq+1);}//以上為找到離散化之后的位置stable_sort(a+1,a+1+n,cmp);bool flag=0;for(int i=1;i<=n&&!flag;i++){int fa=find(a[i].x),fb=find(a[i].y);if(a[i].t) f[min(fa,fb)]=max(fa,fb);//鏈接else if(fa==fb) printf("NO\n"),flag=true;//判答案}if(!flag) printf("YES\n");} }

總結

以上是生活随笔為你收集整理的P1955-[NOI2015]程序自动分析【并查集,离散化】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。