【LOJ】#2129. 「NOI2015」程序自动分析
2024-08-26 02:01:25
题解
开始是想两个并查集的
和A相等,和A不相等
如果AB相等就连
A 相等,B相等
B不相等 A不相等
如果AB不相等就连
A不相等,B相等
B相等,A不相等
但是显然不对,因为和A不相等的不一定和B相等
所以我就gg了,后来发现只要把所有相等的先连上然后看看不相等的有没有在同一集合就行
老年选手连并查集都写跪= =丢人= =
代码
#include <bits/stdc++.h>
//#define ivorysi
#define enter putchar('\n')
#define space putchar(' ')
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eps 1e-8
#define mo 974711
#define MAXN 1000005
#define pii pair<int,int>
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
res = 0;char c = getchar();T f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {putchar('-');x = -x;}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
int T;
int N;
int fa[MAXN * 4];
int X[MAXN],Y[MAXN],e[MAXN];
int num[MAXN * 2],tot;
int getfa(int x) {
return fa[x] == x ? x : fa[x] = getfa(fa[x]);
}
void Solve() {
read(N);
tot = 0;
for(int i = 1 ; i <= N ; ++i) {
read(X[i]);read(Y[i]);read(e[i]);
num[++tot] = X[i];num[++tot] = Y[i];
}
sort(num + 1,num + tot + 1);
tot = unique(num + 1,num + tot + 1) - num - 1;
for(int i = 1 ; i <= tot ; ++i) fa[i] = i;
for(int i = 1 ; i <= N ; ++i) {
X[i] = lower_bound(num + 1,num + tot + 1,X[i]) - num;
Y[i] = lower_bound(num + 1,num + tot + 1,Y[i]) - num;
if(e[i] == 1) {
fa[getfa(X[i])] = getfa(Y[i]);
}
}
for(int i = 1 ; i <= N ; ++i) {
if(e[i] == 0) {
if(getfa(X[i]) == getfa(Y[i])) {
puts("NO");return;
}
}
}
puts("YES");
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
read(T);
while(T--) {
Solve();
}
return 0;
}
最新文章
- 时间“Thu Aug 14 2014 14:28:06 GMT+0800”的转换
- js 漩涡
- Javascript中call、apply、bind函数
- Maven学习 (一) 搭建Maven环境
- GAE初探-一鼻子灰
- 查看修改swap空间大小
- 8款JS框架比较
- 如果一个Object对象可能是数组那么如何对其进行迭代
- Android 网络通信框架Volley基本介绍
- Matlab - 矩阵元素引用
- Myeclipse安装jbpm6
- 反应堆模式(reactor)
- weblogic patch log显示
- Weblogic常见故障常:JDBC Connection Pools【转】
- 配置opensips经验总结
- ubuntu 安装oracle客户端
- Daily Scrum NO.2
- Shell记录-Shell命令(find)
- css-box-shadow
- spring 配置 junit