P1955 [NOI2015]程序自动分析[离散化+并查集]

题目来源:洛谷

题目描述

在实现程序自动分析的过程中,常常需要判定一些约束条件是否能被同时满足。

考虑一个约束满足问题的简化版本:假设x1,x2,x3...代表程序中出现的变量,给定n个形如xi=xj或xi≠xj的变量相等/不等的约束条件,请判定是否可以分别为每一个变量赋予恰当的值,使得上述所有约束条件同时被满足。例如,一个问题中的约束条件为:x1=x2,x2=x3,x3=x4,x4≠x1,这些约束条件显然是不可能同时被满足的,因此这个问题应判定为不可被满足。

现在给出一些约束满足问题,请分别对它们进行判定。

输入输出格式

 

输入格式:

 

从文件prog.in中读入数据。

输入文件的第1行包含1个正整数t,表示需要判定的问题个数。注意这些问题之间是相互独立的。

对于每个问题,包含若干行:

第1行包含1个正整数n,表示该问题中需要被满足的约束条件个数。接下来n行,每行包括3个整数i,j,e,描述1个相等/不等的约束条件,相邻整数之间用单个空格隔开。若e=1,则该约束条件为xi=xj;若�e=0,则该约束条件为xi≠xj;

 

输出格式:

 

输出到文件 prog.out 中。

输出文件包括t行。

输出文件的第 k行输出一个字符串“ YES” 或者“ NO”(不包含引号,字母全部大写),“ YES” 表示输入中的第k个问题判定为可以被满足,“ NO” 表示不可被满足。

 

输入输出样例

输入样例#1:
2
2
1 2 1
1 2 0
2
1 2 1
2 1 1
输出样例#1:
NO
YES
输入样例#2:
2
3
1 2 1
2 3 1
3 1 1
4
1 2 1
2 3 1
3 4 1
1 4 0
输出样例#2:
YES
NO

说明

【样例解释1】

在第一个问题中,约束条件为:x1=x2,x1≠x2。这两个约束条件互相矛盾,因此不可被同时满足。

在第二个问题中,约束条件为:x1=x2,x1=x2。这两个约束条件是等价的,可以被同时满足。

【样例说明2】

在第一个问题中,约束条件有三个:x1=x2,x2=x3,x3=x1。只需赋值使得x1=x1=x1,即可同时满足所有的约束条件。

在第二个问题中,约束条件有四个:x1=x2,x2=x3,x3=x4,x4≠x1。由前三个约束条件可以推出x1=x2=x3=x4,然而最后一个约束条件却要求x1≠x4,因此不可被满足。

【数据范围】

P1955 [NOI2015]程序自动分析[离散化+并查集]

【时限2s,内存512M】

 

解析:

这道题是一个很明显的使用并查集维护具有传递性的信息的思路。

思路:

我们可以把它看作一个图,每个x是其上的一个点,每对xi,xj之间的关系是一条无向边。

由于"="具有传递性,也就是说,当x1=x2,x2=x3时,有x1=x3。因此,我们可以通过维护并查集,使所有相等的x处于同一集合。

然后在对e=0的情况做判断,也就是“≠”,如果查询的某对xi,xj属于同一个集合,那么当前问题就是不可满足的。

具体而言,我们把e=1的关系分到一组,e=0的关系分到另一组,先用并查集维护e=1时的情况,再对e=0时的情况进行查询,如果有两个点属于同一个集合,那么显然不成立。

 

然而这题的毒瘤数据范围在10^9的数量级,我们要在这样一个范围上维护并查集,会TLE掉。

 

默默点开标签,看到离散化,嘿嘿。

离散化又是什么?通俗的讲,离散化就是把无穷大(对计算机而言)集合中的若干个元素映射为有限集合以便于统计的方法。

在这道题目中,我们无须知道具体的xi,xj的值,只需要知道这些数之间的关系,所以我们可以使用离散化。

离散化的模板如下:

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #include<cstring>
 5 #include<ctime>
 6 #include<cstdlib>
 7 #include<algorithm>
 8 #include<queue>
 9 #include<set>
10 #include<map>
11 #define N 100010
12 using namespace std;
13 int a[N],b[N];
14 int main()
15 {
16     int n;
17     cin>>n;
18     int cnt=0;
19     for(int i=1;i<=n;i++){
20         scanf("%d",&a[i]);
21         b[++cnt]=a[i];
22     }
23     sort(b+1,b+n+1);
24     int len=unique(b+1,b+n+1)-(b+1);
25     cout<<len<<endl;
26     for(int i=1;i<=n;i++)
27     {
28         a[i]=lower_bound(b+1,b+len+1,a[i])-b;
29     }
30     for(int i=1;i<=n;i++) cout<<a[i]<<' ';
31     return 0;
32 }

注意本题中有两组亟需离散化的量,我们可以照样把他们放到一个暂存数组中进行离散化,因为他们的相对位置是不变的。

参考代码:

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #include<cstring>
 5 #include<ctime>
 6 #include<cstdlib>
 7 #include<algorithm>
 8 #include<queue>
 9 #include<set>
10 #include<map>
11 #define N 100010
12 using namespace std;
13 int b[N*2],fa[N];
14 struct node{
15     int x,y,e;
16 }a[N];
17 bool cmp(node a,node b){
18     return a.e>b.e;
19 }
20 int get(int x)
21 {
22     if(fa[x]==x) return x;
23     return fa[x]=get(fa[x]);
24 }
25 void merge(int x,int y)
26 {
27     fa[x]=y;
28 }
29 int main()
30 {
31     int n;
32     cin>>n;
33     while(n--)
34     {
35         memset(a,0,sizeof(a));
36         memset(b,0,sizeof(b));
37         memset(fa,0,sizeof(fa));
38         int t,k=0,cnt=0;
39         scanf("%d",&t);
40         
41         for(int i=1;i<=t;i++)
42         {
43             scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].e);
44             b[++cnt]=a[i].x;b[++cnt]=a[i].y;
45         }
46         //离散化 
47         sort(b+1,b+cnt+1);
48         int len=unique(b+1,b+cnt+1)-b;
49         for(int i=1;i<=t;i++){
50             a[i].x=lower_bound(b+1,b+len+1,a[i].x)-b;
51             a[i].y=lower_bound(b+1,b+len+1,a[i].y)-b;
52         }
53         for(int i=1;i<=len;i++) fa[i]=i;
54         sort(a+1,a+t+1,cmp);
55         for(int i=1;i<=t;i++)
56         {
57             if(a[i].e){
58                 int x=get(a[i].x);
59                 int y=get(a[i].y);
60                 if(x!=y) merge(x,y);
61             }
62             else{
63                 int x=get(a[i].x);
64                 int y=get(a[i].y);
65                 //printf("%d follows %d,%d follows %d\n",a[i].x,x,a[i].y,y);
66                 if(x==y){
67                     k=1;
68                     break;
69                 }
70             }
71         }
72         if(k) cout<<"NO"<<endl;
73         else cout<<"YES"<<endl;
74     }
75     return 0;
76 }

 

上一篇:P1955 [NOI2015]程序自动分析 离散化


下一篇:CSS图片水平垂直居中