首页 > 代码库 > 洛谷P1995 程序自动分析
洛谷P1995 程序自动分析
2017-03-18
题目:https://www.luogu.org/problem/show?pid=1955
这道题吗,一看就是并查集,但是范围。。。。。。
好吧,加一个离散化不就好了。。。。。。
不会离散化的请右转去问度娘orz
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 using namespace std; 6 7 struct node{ 8 int x,y; 9 int r; 10 }a[100010]; 11 12 int n,t,c[200210],tot,fa[200210]; 13 int size; 14 bool yes=true; 15 16 int find(int x){ 17 if (fa[x]!=x) fa[x]=find(fa[x]); 18 return fa[x]; 19 } 20 21 int main(){ 22 ios::sync_with_stdio(false); 23 cin>>t; 24 while (t--){ 25 yes=true; 26 cin>>n; 27 tot=0; 28 memset(c,0,sizeof(c)); 29 for (int i=1;i<=2*n;++i) fa[i]=i; 30 for (int i=1;i<=n;++i){ 31 cin>>a[i].x>>a[i].y>>a[i].r; 32 c[++tot]=a[i].x; 33 c[++tot]=a[i].y; 34 } 35 sort(c+1,c+1+tot); 36 size=unique(c+1,c+1+tot)-c-1; 37 for (int i=1;i<=n;++i){ 38 a[i].x=upper_bound(c+1,c+1+size,a[i].x)-c-1; 39 a[i].y=upper_bound(c+1,c+1+size,a[i].y)-c-1; 40 } 41 for (int i=1;i<=n;++i){ 42 if (a[i].r){ 43 int f1=find(a[i].x),f2=find(a[i].y); 44 if (f1!=f2) fa[f1]=f2; 45 } 46 } 47 for (int i=1;i<=n;++i){ 48 if (!a[i].r){ 49 int f1=find(a[i].x),f2=find(a[i].y); 50 if (f1==f2){ 51 yes=false; 52 break; 53 } 54 } 55 } 56 if (yes) cout<<"YES"<<endl; 57 else cout<<"NO"<<endl; 58 } 59 return 0; 60 }
骗分真神奇,暴力出奇迹。
洛谷P1995 程序自动分析
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。