洛谷P1955「NOI2015」题解

发表于 | 评论数： | 阅读次数：

并查集+离散化

题目描述

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

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

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

输入输出格式

输入格式

从文件prog.in中读入数据。

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

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

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

输出格式

输出到文件 prog.out 中。

输出文件包括t行。

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

INPUT & OUTPUT’s examples

Input’s e.g. #1

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

Output’s e.g. #1

1
2
NO
YES

Input’s e.g. #2

1
2
3
4
5
6
7
8
9
10
2
3
1 2 1
2 3 1
3 1 1
4
1 2 1
2 3 1
3 4 1
1 4 0

Output’s e.g. #2

1
2
YES
NO

说明

【样例解释1】

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

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

【样例说明2】

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

在第二个问题中，约束条件有四个：x1=x2,x2=x3,x3=x4,x4≠x1。由前三个约束条件可以推出x1=x2=x3=x4，然而最后一个约束条件却要求x1≠x4，因此不可被满足。

【数据范围】

k4Mdat.png

图源洛谷。

【时限2s，内存512M】

分析

我们先考虑题目中的”相等“这一条件。

我们把每一个变量看做一个节点，一旦有一个相等的条件，那么就把等式两边的变量连一条无向边。

那么两个变量相等当且仅当它们连通。

这样就可以用并查集（冰茶姬）来维护了，我们把变量分成若干个集合，每一个集合表示一个连通块。

首先初始化并查集：（每一个变量单独构成一个集合）

1
for(int i=1;i<=m;i++)UFS[i] = i;

对于每一个相等条件,我们把等式两边的变量所在的集合合并。

而对于每一个不等条件，我们查询一下，如果不等式两边的变量所在的集合相同，那么不能满足。

否则（两个变量不在同一个集合），则满足条件。

结束了？

别急，还没有。

我们发现数据范围中$1 \leq x \leq 10^9$很大。

由于我们只对变量的相等或不等关系关心，那么离散化一下不就好了！

代码

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<iostream>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c))
#define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c))
#define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
#define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
#define lowbit(x) x&(-x)
#define LeftChild(x) x<<1
#define RightChild(x) (x<<1)+1
#define RevEdge(x) x^1
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
namespace FastIO{
    const int BUFSIZE = 1 << 20;
    char ibuf[BUFSIZE],*is = ibuf,*its = ibuf;
    char obuf[BUFSIZE],*os = obuf,*ot = obuf + BUFSIZE;
    inline char getch(){
        if(is == its)
            its = (is = ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is == its)?EOF:*is++;
    }
    inline int getint(){
        int res = 0,neg = 0,ch = getch();
        while(!(isdigit(ch) || ch == '-') && ch != EOF)
            ch = getch();
        if(ch == '-'){
            neg = 1;ch = getch();
        }
        while(isdigit(ch)){
            res = (res << 3) + (res << 1)+ (ch - '0');
            ch = getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os = obuf;
    }
    inline void putch(char ch){
        *os++ = ch;
        if(os == ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)	putch('0');
        else if(res < 0){putch('-');res = -res;}
        int top = 0;
        while(res){
            q[top++] = res % 10 + '0';
            res /= 10;
        }
        while(top--)	putch(q[top]);
    }
    inline void space(bool x){
    	if(!x) putch('\n');
    	else putch(' ');
    }
}
inline void read(int &x){
    int rt = FastIO::getint();
    x = rt;
}
inline void print(int x,bool enter){
    FastIO::putint(x);
    FastIO::flush();
    FastIO::space(enter);
}
/* definitions */
const int MAXN = 1e5 + 7;
const int MAXM = MAXN << 1;
int n,m,disc[MAXM],UFS[MAXM];
struct Analysis{
    int from,to;
    bool can;
};
Analysis Graph[MAXN];
/* functions */
inline void Add_Edge(int from,int to,bool cost,int place){
    #define disp_one(x) (x<<1)-1
    #define disp_two(x) (x<<1)
    Graph[place].from = from;
    Graph[place].to = to;
    Graph[place].can = cost;
    disc[disp_one(place)] = from;
    disc[disp_two(place)] = to;
    #undef disp_one
    #undef disp_two 
}
inline int Find(int x){
    if(UFS[x] == x)return x;
    return UFS[x] = Find(UFS[x]);
}
inline void unionx(int x,int y){
    int findx = Find(x);
    int findy = Find(y);
    UFS[findx] = findy;
}
inline int binary_lower_bound(int x){
    return std::lower_bound(disc + 1,disc + m + 1,x) - disc;
}
inline void work(){
    scanf("%d",&n);
    FOR(i,1,n,1){
        int x,y;
        bool z;
        std::cin>>x>>y>>z;
        Add_Edge(x,y,z,i);
    }
    std::sort(disc + 1,disc + (n << 1) + 1);
    m = std::unique(disc + 1,disc + (n << 1) + 1) - (disc + 1);
    FOR(i,1,m,1)UFS[i] = i;
    FOR(i,1,n,1){
        if(Graph[i].can == true){
            int search_from = binary_lower_bound(Graph[i].from);
            int search_to = binary_lower_bound(Graph[i].to);
            unionx(search_from,search_to);
        }
    }
    FOR(i,1,n,1){
        int search_from = Find(binary_lower_bound(Graph[i].from));
        int search_to = Find(binary_lower_bound(Graph[i].to));
        if(Graph[i].can == false && search_from == search_to){
            puts("NO");
            return;
        }
    }
    puts("YES");
}
int main(int argc,char *argv[]){
    int t;
    scanf("%d",&t);
    FOR(i,1,t,1)work();
    return 0;
}

THE END