BZOJ4195 - [Noi2015]程序自动分析

2017/03/06

题目

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

数据范围

n <= 1E6
i,j <= 1E9

代码

因为太蒻只能写个离线做法:考虑到 zz 的数据范围,先随便离散化一下,然后跑所有相等的条件, 通过并查集求出等价类,然后再验证每个不等的条件是否成立。

 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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <hash_map>
#include <algorithm>
using namespace std;
using __gnu_cxx::hash_map;
const int MAX_Q = 2000000 + 1000;

namespace DisjSet {
    int Fa[MAX_Q];

    void init(int p) {
        for(int i=0;i<p;i++)
            Fa[i] = i;
    }

    int find(int x) { return Fa[x] == x ? x : Fa[x] = find(Fa[x]); }

    void link(int u, int v) {
        Fa[find(u)] = find(v);
    }
};

struct qry {
    int u, v;
    enum {
        Eq,
        Neq
    } typ;
} Q[MAX_Q];

int N;
hash_map<int, int> LUT; int pos = 0;

int main() {
    int T; scanf("%d", &T);

    while(T--) {
        scanf("%d", &N); LUT.clear(); pos = 0;
        
        int op;
        for(int i=0;i<N;i++) {
            scanf("%d %d %d", &Q[i].u, &Q[i].v, &op);
            if(LUT.find(Q[i].u) == LUT.end())
                LUT[Q[i].u] = ++pos;
            if(LUT.find(Q[i].v) == LUT.end())
                LUT[Q[i].v] = ++pos;
            Q[i].typ = op ? qry::Eq : qry::Neq;
        }

        DisjSet :: init(pos + 20);

        for(int i=0;i<N;i++) {
            if(Q[i].typ == qry::Eq) {
                DisjSet :: link( LUT[Q[i].u], LUT[Q[i].v] );
            }
        }

        bool flg = true;
        for(int i=0;i<N;i++) {
            if(Q[i].typ == qry::Neq) {
                if(DisjSet :: find(LUT[Q[i].u]) == DisjSet :: find(LUT[Q[i].v])) {
                    flg = false; break;
                }
            }
        }

        puts(flg ? "YES" : "NO");
    }
}