首页 > 编程语言 >《算法竞赛进阶指南》 第五章 237. 程序自动分析

《算法竞赛进阶指南》 第五章 237. 程序自动分析

时间:2023-04-20 15:56:55浏览次数:48  
标签:约束条件 NoEqualV 进阶 get int mm 第五章 237 find

地址 https://www.acwing.com/problem/content/239/

在实现程序自动分析的过程中,常常需要判定一些约束条件是否能被同时满足。

考虑一个约束满足问题的简化版本:假设 x1,x2,x3,… 代表程序中出现的变量,
给定 n 个形如 xi=xj 或 xi≠xj 的变量相等/不等的约束条件,请判定是否可以分别为每一个变量赋予恰当的值,
使得上述所有约束条件同时被满足。

例如,一个问题中的约束条件为:x1=x2,x2=x3,x3=x4,x1≠x4,
这些约束条件显然是不可能同时被满足的,因此这个问题应判定为不可被满足。

现在给出一些约束满足问题,请分别对它们进行判定。

输入格式
输入文件的第 1 行包含 1 个正整数 t,表示需要判定的问题个数,注意这些问题之间是相互独立的。

对于每个问题,包含若干行:

第 1 行包含 1 个正整数 n,表示该问题中需要被满足的约束条件个数。

接下来 n 行,每行包括 3 个整数 i,j,e,描述 1 个相等/不等的约束条件,相邻整数之间用单个空格隔开。
若 e=1,则该约束条件为 xi=xj;若 e=0,则该约束条件为 xi≠xj。

输出格式
输出文件包括 t 行。

输出文件的第 k 行输出一个字符串 YES 或者 NO,YES 表示输入中的第 k 个问题判定为可以被满足,NO 表示不可被满足。

数据范围
1≤n≤105
1≤i,j≤109
输入样例:
2
2
1 2 1
1 2 0
2
1 2 1
2 1 1
输出样例:
NO
YES

解答
使用并查集即可, 注意不是加权或者扩展域并查集,因为a!=b 和c!=b 的情况不能说明a和c的关系,所以使用边权扩展域这种非a即b否则为c的情况。
同时注意数值较少但是取值范围很大,所以并查集的数组范围不能取这么多,需要离散化

#include <vector>
#include <unordered_map>
#include <iostream>
using namespace std;

const int N = 2000010 +10;
unordered_map<int, int> mm; int midx;
int n,t;
int p[N];
vector<pair<int, int>> NoEqualV;

void initUnion() {
	for (int i = 0; i < N; i++) {
		p[i] = i;
	}
}

int get(int x) {
	if (mm.count(x) == 0) {
		mm[x] = ++midx;
		return midx;
	}
	return mm[x];
}

int find(int x) {
	if (p[x] != x) p[x] = find(p[x]);
	return p[x];
}

int main()
{
	cin >> t;
	while (t--) {
		cin >> n;
		int x, y, c;
		initUnion();
		NoEqualV.clear();
		mm.clear();
		for (int i = 0; i < n; i++) {
			cin >> x >> y >> c;
			int xn = get(x);
			int yn = get(y);
			if (c == 1) {
				//合并所有的相等项
				int fx = find(xn); int fy = find(yn);
				p[fx] = fy;
			}
			else if (c == 0) {
				NoEqualV.push_back({ xn,yn });
			}
		}

		//再次查找不等的式子 查看是否有冲突
		int conflict = 0;
		for (int i = 0; i < NoEqualV.size(); i++) {
			int an = NoEqualV[i].first; int bn = NoEqualV[i].second;
			//int an = get(a); int bn = get(b);
			int fa = find(an); int fb = find(bn);
			if (fa == fb) {
				conflict = 1; break;
			}
		}

		if (1 == conflict) {cout << "NO" << endl;}
		else {	cout << "YES" << endl;}
	}


	return 0;
}

标签:约束条件,NoEqualV,进阶,get,int,mm,第五章,237,find
From: https://www.cnblogs.com/itdef/p/17337134.html

相关文章

  • vue全家桶进阶之路43:Vue3 Element Plus el-form表单组件
    在ElementPlus中,el-form是一个表单组件,用于创建表单以便用户填写和提交数据。它提供了许多内置的验证规则和验证方法,使表单验证更加容易。使用el-form组件,您可以将表单控件组织在一起,并对表单进行验证,以确保提交的数据符合预期的格式和要求。该组件具有以下特性:支持内置......
  • 05_面向对象(进阶)
    五、面向对象(进阶)5.1关键字:this5.1.1this的使用场景目前出现的问题?解决方案?问题:我们在声明setXxx方法时,通过形参给对应的属性赋值。如果形参名和属性名同名,那么该如何在方法内区分这两个变量呢?解决方案:使用this。使用this修饰的变量,表示的是属性(成员变量);没有用this......
  • Vue进阶(六十二):理解$nextTick()
    一、实例介绍有一个div,默认用了v-if隐藏,点击按钮之后,改变v-if的值让他显示出来,并且取到div中的值:<divid=app><divid="div"v-if="showDiv">我是显示文本</div><button@click="showAndGetText">获取内容</button></div><script>va......
  • 动力节点2023版MyBatisPlus教程【进阶篇】
    来自B站动力节点最新版的MybatisPlus教程,整理了笔记——第四章高级篇4【高级篇】4.1主键策略4.1.1主键生成策略介绍首先大家先要知道什么是主键,主键的作用就是唯一标识,我们可以通过这个唯一标识来定位到这条数据。当然对于表数据中的主键,我们可以自己设计生成规则,生成主键。......
  • vue全家桶进阶之路37:Vue3 状态管理
    Vue3的状态管理主要是通过Vuex4来实现。Vuex是一个专为Vue.js应用程序开发的状态管理模式,它采用集中式存储管理应用的所有组件的状态,并以相应的规则保证状态以一种可预测的方式发生变化。在Vue3的状态管理中,以下是各个属性的作用:state:存储应用程序中的状态数据。它可以......
  • vue全家桶进阶之路37:Vue3 路由守卫
    在Vue.js3.x中,我们可以使用路由守卫来拦截路由的跳转,从而实现一些功能,例如:登录验证、页面权限控制等。Vue.js3.x中的路由守卫和Vue.js2.x中的基本相同,都包含了beforeEach、beforeResolve和afterEach等钩子函数。下面是一些常见的路由守卫用法示例:beforeEachbefo......
  • 05_面向对象(进阶)
    目录五、面向对象(进阶)5.1关键字:this5.1.1this的使用场景5.1.2this调用构造器5.2面向对象特征二:继承5.2.1继承性的理解5.2.2继承的优点5.2.3继承的格式5.2.4默认的父类5.2.5补充说明5.3封装性中4种权限修饰5.4方法的重写(overwrite/override)5.4.1方法重写概述5.4.2方......
  • vue全家桶进阶之路33:Vue3 计算属性computed
    在Vue3中,计算属性可以使用computed函数来定义。computed函数接受两个参数:第一个参数是一个函数,该函数返回计算属性的值;第二个参数是一个可选的配置对象,可以包含getter和setter函数,以及控制计算属性缓存的缓存配置。Vue3中的计算属性与Vue2中的计算属性相比有以下几个变化:使用......
  • 【进阶13】【自学笔记】Python logging模块封装
    一、定义  Pythonlogging模块是一个可以通过控制日志级别、输出位置等方式来实现记录日志的模块。logger对象的不同方法来记录不同级别的日志。  其中,debug()方法用于记录debug级别的日志,info()方法用于记录info级别的日志,warning()方法用于记录warning级别的日志,err......
  • CodeStar2023年春第5周周赛普及进阶组
    T1:分段求平均数本题难度中等,划分型DP问题。用dp[i]表示前\(i\)个数最少划分成几段,对\(j=1,2,\cdots,i-1\)判断从\(a_j\)到\(a_i\)划分成一段时,平均数是否为整数,如果是整数,就更新\(dp[i]=\max(dp[i],dp[j-1]+1)\)初始值:\(dp[i]=i\)代码实现#include<b......