P1955 [NOI2015]程序自动分析

2019-08-06 22:55:31


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

题面描述

很简单:

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

思路:

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

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

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

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

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

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

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]; 
    }
}

下面贴出全篇代码:

#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优化才能过。