P1955 [NOI2015] 程序自动分析

基本思路

考虑到了不等号的不可传递性，所以决定只开相等的并查集。

然后突发奇想，觉得可以在找父亲的过程中判断是不是冲突。

然而这样就不能路径压缩，显然超时。

并且，根本没看清楚数据范围，实际上这题的数很大，裸开数组会爆炸。

这是一开始的代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>

const int N = 1e8 + 10;

int t, n;
int x, y, z;
int fa[N];

int findSet(int x)
{
	if (x == fa[x]) return x;
	return findSet(fa[x]);
}

bool check(int x, int y)
{
	if (y == fa[x]) return false;
	if (x == fa[x]) return true;
	return check(fa[x], y);
}

void merge(int x, int y)
{
	int fx = findSet(x), fy = findSet(y);
	if (fx == fy) return;
	fa[fx] = fy; 
}

int main()
{
 	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	std::cin >> t;
	while(t--)
	{
		bool ok = true;
		memset(fa, 0, sizeof(fa));
		std::cin >> n;
		while(n--)
		{
			std::cin >> x >> y >> z;
			if (z == 1)
			{
				if (!fa[x]) fa[x] = x;
				if (!fa[y]) fa[y] = y;
				merge(x, y);
			}
			else if (ok) ok = (check(x, y) && check(y, x));
		}
		if (ok) std::cout << "YES\n";
		else std::cout << "NO\n";
	}
	return 0;
}

改进思路

针对超时

其实完全可以继续路径压缩，然后对于一个需要 \(x \neq y\) 的情况，直接在相等数构成的并查集里面找二者的父亲，只要相等，就说明冲突。

针对数据

离散化就行。

• 先做好基本的排序、去重。

  这里用std::unique，把重复元素都移到vector尾部。然后dt.erase(std::unique(dt.begin(), dt.end()), dt.end());来去重。

• 然后进行离散化。

  • 本题可以离散化是因为只要区分出不同数据即可，不需要知道数据本身是什么。

  • 即按照数据在数组中第几大来给数据一个新的映射值。

  • void getLs() 
    {
    	x = lower_bound(dt.begin(), dt.end(), x) - dt.begin();
    	y = lower_bound(dt.begin(), dt.end(), y) - dt.begin();
    	fa[x] = x, fa[y] = y;
    }
    

代码实现

第一次尝试面向对象风格

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>

const int N = 1e6 + 10;

int t, n;
int fa[N];
std::vector <int> dt;

class Node{
	private:
		int findSet(int x)
		{
			return x == fa[x] ? x : fa[x] = findSet(fa[x]);
		}
	public:
		int x, y, z; 
		void read()
		{
			std::cin >> x >> y >> z;
		}
		bool operator < (const Node& rhs) const {
			return z > rhs.z;
		}
		void getLs()
		{
			x = lower_bound(dt.begin(), dt.end(), x) - dt.begin();
			y = lower_bound(dt.begin(), dt.end(), y) - dt.begin();
			fa[x] = x, fa[y] = y;
		}
		void merge()
		{
			int fx = findSet(x), fy = findSet(y);
			if (fx == fy) return;
			fa[fx] = fy; 
		}
		bool check()
		{
			return findSet(x) == findSet(y);
		}
		void outPut()
		{
			std::cout << x <<" "<< y << " " << z <<std::endl;
		}
}a[N];

int main()
{
 	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	std::cin >> t;
	while(t--)
	{
		memset(fa, 0, sizeof(fa));
		bool ok = true;
		std::cin >> n;
		for (int i = 1; i <= n; i++) 
		{
			a[i].read();
			dt.push_back(a[i].x), dt.push_back(a[i].y); 
		}
		std::sort(a + 1, a + n + 1);
		std::sort(dt.begin(), dt.end());
		dt.erase(std::unique(dt.begin(), dt.end()), dt.end());
		for (int i = 1; i <= n; i++) a[i].getLs();
		for (int i = 1; i <= n; i++)
		{
			if (a[i].z) a[i].merge();
			else if (a[i].check())
			{
				ok = false;
				std::cout << "NO\n"; 
				break;
			}
		}
		if (ok) std::cout << "YES\n";
	}
	return 0;
}