并查集+ 离散化
首先本题的数据范围很大,需要离散化,
STL离散化代码://dat是原数据,id是编号,sub是数据的副本 sort(sub + 1, sub + tot + 1); size = unique(sub + 1, sub + tot + 1) - sub - 1; for(int i = 1; i <= tot; i++) { id[i] = lower_bound(sub + 1, sub + size + 1, dat[i]) - sub; } 并查集所能维护的是具有传递性的关系,比如本题中 等于 就是这样的关系,而不等就不是.
所以本题的思路非常简单,首先处理出来等于的关系,对于每一个不等的关系找矛盾即可#include#include #include #include #include using namespace std;const int MAXN = 100005;int init() { int rv = 0, fh = 1; char c = getchar(); while(c < '0' || c > '9') { if(c == '-') fh = -1; c = getchar(); } while(c >= '0' && c <= '9') { rv = (rv<<1) + (rv<<3) + c - '0'; c = getchar(); } return fh *rv;}struct opt{ int x, y; bool f;}e[MAXN];int T, n, id[MAXN<<1], dat[MAXN<<1], tot, sub[MAXN<<1], size, fa[MAXN<<2];int find(int x) { if(fa[x] != x) fa[x] = find(fa[x]); return fa[x];}void merge(int x, int y) { if(x == y) return; int r1 = find(x), r2 = find(y); if(r1 != r2) fa[r1] = r2;}int main() { T = init(); while(T--){ memset(e, 0, sizeof(e)); n = init(); tot = 0; size = 0; for(int i = 1; i <= n; i++) { e[i].x = init(); e[i].y = init(); e[i].f = init(); tot++; dat[tot] = sub[tot] = e[i].x; tot++; dat[tot] = sub[tot] = e[i].y; } sort(sub + 1, sub + tot + 1); size = unique(sub + 1, sub + tot + 1) - sub - 1; for(int i = 1; i <= tot; i++) { id[i] = lower_bound(sub + 1, sub + size + 1, dat[i]) - sub; } for(int i = 1; i <= size; i++) { fa[i] = i; } /*for(int i = 1; i <= tot ; i++) printf("%d %d\n", id[i], dat[i]); printf("\n");*/ bool fff = 0; for(int i = 1; i <= n; i++) { e[i].x = id[i * 2 - 1]; e[i].y = id[i * 2]; if(e[i].f) { merge(e[i].x, e[i].y); } } for(int i = 1; i <= n; i++) { if(!e[i].f) { if(find(e[i].x) == find(e[i].y)) {fff = 1;break;} } } if(!fff) { printf("YES\n"); }else printf("NO\n"); } return 0;}