P1955 [NOI2015] 程序自动分析

算法1

(离散化+并查集)

没想到的点：

由于数据范围很大1e9,因此需要采用离散化，从而降低时间复杂度

主要思想

1.约束条件有相等/不相等，不难发现，相等的约束条件是属于一个集合的 -- 因此需要用到并查集思想

我们按照e的大小进行排序，从而完成先处理 e = 1 的所有情况

3.并查集：

初始化：一开始所有数都是一个独立的集合

合并集合：当e = 1时，我们合并两个集合；

4.矛盾式： 当e = 0 时，两个数属于同一个集合，则矛盾，输出“NO”；

离散化：

由于我们处理的数<=le9，显然这个数很大，如果直接开le9个集合，那么会爆内存/超时

因此我们采用离散化的思想，从而降低复杂度

离散化的三步骤：

1.对所有待离散化的值进行排序

2.去重

3.二分查找离散化后的值；

这里我们把一个很大的数，映射到下标为1~N的离散化数组当中

注意：

离散化数组的大小至少需要开2倍，因为一开始我们存放两个数，我这里比较安全的开了4倍；

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6+10;

int T,n;
int p[N]; //并查集
int book[4*N];  //离散化后的值 ,数组的大小至少要开两倍 
//约束条件
struct node{
	int x,y,e;
}a[N];
//按照升序进行排序 
bool cmp(node u,node v){
	return u.e > v.e;
}
int init(int x){
	for(int i=1;i<=x;i++) p[i] = i;
}
int find(int x){
	if(x != p[x]) p[x] = find(p[x]);
	return p[x];
}
int main(){
	cin >> T;
	
	while(T--){
		
		int cnt = 0;  //映射到下标从0-N的数组 
		memset(a,0,sizeof a); 
		memset(p,0,sizeof p);
		memset(book,0,sizeof book);
		
		bool flag = 1;   //满足条件的情况 
		cin >> n;
		for(int i=1;i<=n;i++){
			cin >> a[i].x >> a[i].y >> a[i].e;
			
			//待离散化的值全部放入book 数组当中 
			book[++cnt] = a[i].x;
			book[++cnt] = a[i].y; 
		}
	
		//离散化三步骤
		//1.排序 
		sort(book+1,book+1+cnt);
		//2.去重 
		int re = unique(book+1,book+1+cnt) - book; //返回不重复的元素个数 
	
		//3.二分查找-离散化后的值在新数组的下标 
		for(int i = 1;i <= n;i++){
			//返回x,y 在book中的下标 - 达到离散化的目的 
			a[i].x = lower_bound(book+1,book+1+re,a[i].x) - book;   //返回的是下标 
			a[i].y = lower_bound(book+1,book+1+re,a[i].y) - book;
		} 
		
//		for(int i=1;i<=n;i++){
//			cout << a[i].x <<a[i].y << a[i].e<<endl;
//		} 
		
		//按照e的情况进行排序 ，先处理所有1的情况 
		init(re);
		sort(a+1,a+1+n,cmp);
		for(int i=1;i<=n;i++){
			int f1 = find(a[i].x), f2 = find(a[i].y);
			if(a[i].e){
				p[f1] = f2;
			}
			else if(f1 == f2){  //属于一个集合 ，成为矛盾式 
				flag = 0;
				break;
			}
		} 
		if(flag) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	return 0;
}