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

[NOI2015] 程序自动分析

题目描述

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

考虑一个约束满足问题的简化版本：假设 $x_1,x_2,x_3,\cdots$ 代表程序中出现的变量，给定 $n$ 个形如 $x_i=x_j$ 或 $x_i\ne x_j$ 的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。例如，一个问题中的约束条件为：$x_1=x_2,x_2=x_3,x_3=x_4,x_4\ne x_1$，这些约束条件显然是不可能同时被满足的，因此这个问题应判定为不可被满足。

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

输入格式

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

对于每个问题，包含若干行：

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

输出格式

输出包括 $t$ 行。

输出文件的第 $k$ 行输出一个字符串 YES 或者 NO（字母全部大写），YES 表示输入中的第 $k$ 个问题判定为可以被满足，NO 表示不可被满足。

样例 #1

样例输入 #1

2
2
1 2 1
1 2 0
2
1 2 1
2 1 1
1
2
3
4
5
6
7

样例输出 #1

NO
YES
1
2

样例 #2

样例输入 #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
1
2
3
4
5
6
7
8
9
10

样例输出 #2

YES
NO
1
2

提示

【样例解释1】

在第一个问题中，约束条件为：$x_1=x_2,x_1\ne x_2$。这两个约束条件互相矛盾，因此不可被同时满足。

在第二个问题中，约束条件为：$x_1=x_2,x_1=x_2$。这两个约束条件是等价的，可以被同时满足。

【样例说明2】

在第一个问题中，约束条件有三个：$x_1=x_2,x_2=x_3,x_3=x_1$。只需赋值使得 $x_1=x_2=x_3$，即可同时满足所有的约束条件。

在第二个问题中，约束条件有四个：$x_1=x_2,x_2=x_3,x_3=x_4,x_4\ne x_1$。由前三个约束条件可以推出 $x_1=x_2=x_3=x_4$，然而最后一个约束条件却要求 $x_1\ne x_4$，因此不可被满足。

【数据范围】

注：实际上 $n\le 10^6$ 。

分析

1. 此题就是离散化结合并查集来做，先离散化i和j的值，然后并查集判断，需要注意一下变量的区别，n是num的组数，idx是需要离散的值的个数，len是离散化后的数组长度
2. 离散化
   离散化用在如下的情况之下，用权值开辟数组空间时，权值太大数组会爆，然后如果仅仅需要的是相对大小，而不是实际值，比如a[1]=1999 ,a[2]=19999 ,a[3]=19999，可以用1 2 2来表示将a[i]离散化为1到n这些索引；离散化有三步：1.去重（可以用到unique去重函数）2.排序 3.二分索引（可以用到lower_bound函数）；离散化参考：离散化：两种离散化方式详解、c++常用技巧——离散化 （南昌理工ACM集训队）、【基础算法】离散化 视频
   
   将序列长度为6的序列离散化后的结果如下：
   
3. 并查集
   等号显然具有传递性:a=b ,b=c →a=c，所以可以用并查集处理，先处理所以e等于1的等式（利用自定义排序cmp），然后判断即可；并查集的f数组初始化不能忘；

#include

using namespace std;

typedef unsigned long long ull;
const int N = 1e6 + 10;

struct node {
    int x, y, e;
} num[N];

bool cmp(node a, node b) {
    //先处理相等的关系（e=1）
    return a.e > b.e;
}

int f[N];//把本该10^9离散化为10^6
int a[N * 3], idx;//离散的数组,数组至少要开两倍大小，因为刚开始要同时记录两个值
int len;//离散化后的实际数组a的长度
int t, n;

int find(int x) {
    if (x == f[x])
        return x;
    return f[x] = find(f[x]);
}

void merge(int x, int y) {
    x = find(x);
    y = find(y);
    f[x] = y;
}

int main() {
    cin.tie(0);
    cin >> t;
    while (t--) {
        cin >> n;
        memset(f, 0, sizeof f);
        memset(a, 0, sizeof a);
        memset(num, 0, sizeof num);
        idx = 0;

        for (int i = 1; i <= n; ++i) {
            cin >> num[i].x >> num[i].y >> num[i].e;
            //把i,j值存下来，然后离散化他们存在a中
            a[++idx] = num[i].x;
            a[++idx] = num[i].y;
        }
        //对所有的i j进行离散化:

        //排序(n是num的组数，idx是需要离散的值的个数，len是离散化后的数组长度)
        sort(a + 1, a + 1 + idx);
        //去重,返回一个迭代器，指向数组中去重后不重复的序列中华最后那一个元素的下一个元素
        len = unique(a + 1, a + 1 + idx) - (a + 1);
        //二分
        for (int i = 1; i <= n; ++i) {
            //a已经有序了，看看num[i].x的值在a中的索引排在多少，赋给它本身
            num[i].x = lower_bound(a + 1, a + 1 + len, num[i].x) - (a + 1);
            num[i].y = lower_bound(a + 1, a + 1 + len, num[i].y) - (a + 1);
        }
       
        //离散化完成，开始并查集
        //为了下面能先处理等式的操作
        sort(num + 1, num + 1 + n, cmp);
        for (int i = 1; i <= len; i++)
            f[i] = i;
        int flag = 1;
        for (int i = 1; i <= n; ++i) {
            int x = num[i].x, y = num[i].y, e = num[i].e;
            if (e == 1) {
                merge(find(x), find(y));
            } else {
                if (find(x) == find(y)) {
                    cout << "NO" << endl;
                    flag = 0;
                    break;
                }
            }
        }
        if (flag)
            cout << "YES" << endl;
    }
    return 0;
}


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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87