【LuoguP1955】【BZOJ4195】【NOI2015】程序自动分析
题目链接1: https://www.luogu.org/problemnew/show/P1955
题目链接2: https://www.lydsy.com/JudgeOnline/problem.php?id=4195
引言
最近变得越来越颓废. 介于好长时间没更新博客, 强行水一篇题解.
这道题没看题解15分钟就A了, 真的有点水了…
分析
题意大概就是有 N 个关系, 每个代表X1 = X2 或者 X1 ≠ X2, 求出这些关系能不能成立.
很容易就想到并查集, 先将相等的X合并, 然后判断不等关系的两个变量在不在一个并查集里就行了.那么就只需要排下序, 先进行合并操作再去判断.
判断不等关系过程中发现X1和X2在同一个并查集里, 那直接输出NO就行了.
然而X的下标可能会很大. 所以考虑离散化, 那么肯定直接上map.
输入的时候就离散化, 然后排个序, 打完合并和查询就AC了.
不过map常数巨大, 需要开O2稳过.
代码
评测详情（O2）:
Accepted 100
用时: 1623ms / 内存: 11960KB
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
| #include <iostream>
#include <stdio.h>
#include <map>
#include <algorithm>
using namespace std;
int t, n, f[200001], mptr, cnt, flag;
struct date {
int x, y, d;
bool operator<(const date &d2) const {
return d > d2.d;
}
} dat[100001];
int query(int x) {
if(f[x] == x) return x;
return f[x]= query(f[x]);
}
map< int, int > m;
int main() {
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
mptr= cnt= flag= 0;
m.clear();
for(int i= 1; i <= n; i++) {
scanf("%d%d%d", &dat[i].x, &dat[i].y, &dat[i].d);
if(!m.count(dat[i].x)) m[dat[i].x]= ++mptr;
if(!m.count(dat[i].y)) m[dat[i].y]= ++mptr;
dat[i].x= m[dat[i].x], dat[i].y= m[dat[i].y];
cnt+= dat[i].d;
}
sort(dat + 1, dat + n + 1);
for(int i= 1; i <= mptr; i++) f[i]= i;
for(int i= 1; i <= cnt; i++) {
int fx= query(dat[i].x);
f[query(dat[i].y)]= fx;
}
for(int i= cnt + 1; i <= n; i++) {
if(query(dat[i].x) == query(dat[i].y)) {
printf("NO\n");
flag= 1;
break;
}
}
if(!flag) printf("YES\n");
}
return 0;
}
|
