洛谷P1955 [NOI2015]程序自动分析

红太狼 2023-03-04 05:25 163阅读 0赞

# 洛谷P1955 \[NOI2015\]程序自动分析 #

![博客图片][format_png]

## 题目链接 ##

[洛谷P1955 程序自动分析][P1955]

## 题目概述 ##

存在 n n n个变量 x 1 , x 2 , … , x n x\_1,x\_2,\\dots,x\_n x1,x2,…,xn,给出这 n n n个变量之间的 n n n个约束条件 x i = x j o r x i ≠ x j x\_i = x\_j \\ or \\ x\_i \\neq x\_j xi=xjorxi=xj判断这些是否可以同时满足,如果可以输出`YES`,否则输出`NO`.一组测试包含多个测试,输入的开始给出测试的个数,每个测试相互独立.变量之间的约束条件输入的格式为 i j e i\\quad j\\quad e ije,如果 e = 1 e = 1 e=1说明 x i = x j x\_i = x\_j xi=xj,如果 e = 0 e=0 e=0说明 x i ≠ x j . x\_i \\neq x\_j. xi=xj.

## 题目分析 ##

可以先根据相等的条件把相等的变量划分到一个集合中,然后逐一的判断每个不相等的条件,取出这两个变量 x i , x j x\_i,x\_j xi,xj如果 x i , x j x\_i,x\_j xi,xj属于同一个值相等的集合,那么这个约束条件不满足,可以直接输出`NO`,当所有的不相等的约束条件都满足时输出`YES`.

并查集就是这样一种支持将元素按所属的集合进行分类,可以找到集合中任意一个元素所属的集合,核心操作是`union_set(x,y)`和`find_set(x)`.以每个集合的**树高用于合并时的优化**,和查询时采用**路径压缩**在找到元素所属集合的根节点后,把从根节点到这个元素结点路径上的所有结点的前驱改为根节点,从而在一次 O ( l o g ( n ) ) O(log(n)) O(log(n))的时间福再度查询后,下一次可以以 O ( 1 ) O(1) O(1)的时间复杂度获得这个元素的集合的根节点.经过这样的`union_set`和`find_set`操作,最后得到的并查集的一个类似于这种形式:

...

\*\*注意:\*\*但是题目中对于 i , j i,j i,j范围的限定是 1 ≤ i , j ≤ 1 0 9 1\\leq i,j \\leq 10^9 1≤i,j≤109,如果直接开一个 1 0 10 10^\{10\} 1010的数组,外加一些其它的空间开销,是没法分配这样大的空间的,如果数组开的小,会有一个测试点出现`RE`,一个可行的方案是对输入的数据进行离散化处理,输入的数据最多有 2 n 2n 2n个,而 n n n的范围是 1 ≤ n ≤ 1 0 5 1\\leq n \\leq 10^5 1≤n≤105,空间开销比较小,假设一组输入的约束条件是:

10000 1999999 1
    199999 99999999 0
    92713821 23713324 1
    10000 23713324 0

很明显这样的数据如果直接用数组下标映射,数组的开销非常大,但实际上输入的数据非常少,把输入的每一个变量存储起来,得到这样的一个序列:

10000 1999999 199999 99999999 92713821 23713324 10000 23713324

然后按升序进行排列去重,得到:

10000 199999 1999999 23713324 92713821 99999999

这样就建立了原来数据和现在数据在序列中下标的映射:  
 b u f \[ 0 \] = 10000 , b u f \[ 1 \] = 199999 , … buf\[0\]=10000,buf\[1\]=199999,\\dots buf\[0\]=10000,buf\[1\]=199999,…  
如果需要查询某个数 x x x在上面的有序序列中,可以用`STL`标准库里面的`lower_bound`方法,返回值是区间 \[ f i r s t , l a s t ) \[first,last) \[first,last)第一个不小于 x x x的数在这个区间的位置,如果没有,那么返回 l a s t last last,因为上面的序列是单调递增的,并且查询的 x x x一定位于其中,所以最后得到的一定是数 x x x在 b u f buf buf中的位置.

经过上面的序列化处理后,利用并查集的模板可以轻松方便的解决这个题目

## 代码实现 ##

/*
     * @Author: Shuo Yang
     * @Date: 2020-08-01 08:08:32
     * @LastEditors: Shuo Yang
     * @LastEditTime: 2020-08-01 10:50:03
     * @FilePath: /Code/luogu/P1955.cpp
     */ 
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N = 1e6+5;
    int s[N];
    int heights[N];
    int buf[N];
    
    //并查集模板
    
    void init_set(){
        
        memset(heights, 0,sizeof(heights));
        for(int i = 0;i < N; ++i)
            s[i] = i;
    }
    
    int find_set(int x){
        
        int r = x;
        while( s[r] != r){
        
            r = s[r];
        }
        int i = x;
        while( i != r){
        
            int j = s[i];
            s[i] = r;
            i = j;
        }
        return r;
    }
    
    
    void union_set(int x, int y){
        
        x = find_set(x);
        y = find_set(y);
        if( heights[x] == heights[y]){
        
            heights[x]++;
            s[y] = x;
        }else{
        
            if( heights[x] < heights[y])
                s[x] = y;
            else
                s[y] = x;
        }
    }
    
    //这道题实际处理的部分
    
    struct node{
        
        int a,b;
    };
    
    node equ[N];
    node nequ[N];
    int cnt = 0;
    
    int get_index(int x){
        
        return lower_bound(buf, buf+cnt, x) - buf;
    }
    
    void solve(int n, int m){
        
        init_set();
        for(int i = 0; i < n; ++i){
        
            union_set(get_index(equ[i].a), get_index(equ[i].b));
        }
        for(int i = 0; i < m; ++i){
        
            if(find_set(get_index(nequ[i].a)) == find_set(get_index(nequ[i].b))){
        
                cout<<"NO"<<endl;
                return;
            }
        }
        cout<<"YES"<<endl;
    }
    
    int main(int argc, const char** argv) {
        
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
        int t;
        cin>>t;
        while(t--){
        
            int k;
            cin>>k;
            int n = 0;
            int m = 0;
            cnt = 0;
            for(int i = 0; i < k; ++i){
        
                int a,b,f;
                cin>>a>>b>>f;
                if(f==1){
        
                    equ[n++] = {
        a,b};
                }else{
        
                    nequ[m++] = {
        a,b};
                }
                buf[cnt++] = a;
                buf[cnt++] = b;
            }
            //排序去重
            sort(buf, buf+cnt);
            cnt = unique(buf, buf+cnt)-buf;
            solve(n,m);
        }
        return 0;
    }

## 其它 ##

[format_png]: /images/20230208/ee4b46ed1c9f4ccb8801318e0f35c125.png
[P1955]: https://www.luogu.com.cn/problem/P1955