P1955 [NOI2015]程序自动分析

我的思路貌似和大家不一样哈……

题面描述

很简单:

给出许多相等和不相等的条件,判断是否矛盾。

思路:

其实这道题连蓝题都不到……

使用并查集统计不同的关系,再枚举相同的,看是否矛盾即可。

发现i,j极大,冷静,不要写哈希

记住,先看一下可不可以使用map

发现可以,开两个map,一个用于存储并查集的数组,另一个则存储数组中有没有出现过这个数,再编写一个函数,用于返回这个数组上的数的引用,这样如果下面要改的话很方便。

这个函数:(unordered_map是啥看我的文章)

1
2
3
4
5
6
7
8
9
10
long long n,nd,p,di[1000005],dj[1000005];
unordered_map<long long,long long> idm;
unordered_map<long long,bool> idb;
long long &id(long long x){
if(idb[x]) return idm[x];//如果已经有了,就直接返回数组中的数
else {//否则返回x
idb[x]=1,idm[x]=x;
return idm[x];
}
}

下面贴出全篇代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
using namespace std;
long long n,nd,p,di[1000005],dj[1000005];
unordered_map<long long,long long> idm;//存储并查集数组
unordered_map<long long,bool> idb;//存储是否出现过
long long &id(long long x){ //返回的是引用
if(idb[x]) return idm[x];
else {
idb[x]=1,idm[x]=x;
return idm[x];
}
}
long long find(long long x){
if(id(x)==x) return x;
return id(x)=find(id(x));
}
void unite(long long x,long long y){
long long xi=find(x),yi=find(y);
id(xi)=yi;//因为是引用,所以可以直接这样写
}
int main(){
ios::sync_with_stdio(false);//读入优化
cin>>p;
for(int np=0;np<p;np++){
idm.clear();//清空map
idb.clear();
nd=0;
bool flag=0;
cin>>n;
int i,j,e;
for(int a=0;a<n;a++){
cin>>i>>j>>e;
if(e==0){//如果两者不相同,把它们存起来
di[nd]=i,dj[nd]=j;
nd++;
}
else unite(i,j);//否则将它们存入并查集
}
for(int a=0;a<nd;a++){
if(find(di[a])==find(dj[a])){//如果两者本应相等,却不相等
cout<<"NO\n";
flag=1;
break;
}
}
if(!flag)cout<<"YES\n";
}
return 0;
}

再说一下,这个代码不开优化是不过的,必须开O2优化才能过。