洛谷 [P1995] 程序自动分析

并查集+ 离散化

首先本题的数据范围很大,需要离散化,

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 <iostream>

#include <cstdio>

#include <algorithm>

#include <cstdlib>

#include <cstring>

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;

}

巴特西

洛谷 [P1995] 程序自动分析

并查集+ 离散化

最新文章

热门文章