洛谷P1995 程序自动分析

2017-03-18

题目：https://www.luogu.org/problem/show?pid=1955

这道题一般能看出来是并查集。

但是，i、j的范围似乎有一点鬼畜。。。。。。

但是n的范围还是比较友好的。

所以，我们要用的一招叫做离散化。

离散化，针对只在乎大小，而不在乎具体值的数据使用。

如果不会离散化的话，问度娘或点我>_<。

 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 }

戳我>_<

骗分真神奇，暴力出奇迹。