当前位置: 首页 > news >正文

P1993 小 K 的农场

小 K 的农场

题目描述

小 K 在 MC 里面建立很多很多的农场,总共 n n n 个,以至于他自己都忘记了每个农场中种植作物的具体数量了,他只记得一些含糊的信息(共 m m m 个),以下列三种形式描述:

  • 农场 a a a 比农场 b b b 至少多种植了 c c c 个单位的作物;
  • 农场 a a a 比农场 b b b 至多多种植了 c c c 个单位的作物;
  • 农场 a a a 与农场 b b b 种植的作物数一样多。

但是,由于小 K 的记忆有些偏差,所以他想要知道存不存在一种情况,使得农场的种植作物数量与他记忆中的所有信息吻合。

输入格式

第一行包括两个整数 n n n m m m,分别表示农场数目和小 K 记忆中的信息数目。

接下来 m m m 行:

  • 如果每行的第一个数是 1 1 1,接下来有三个整数 a , b , c a,b,c a,b,c,表示农场 a a a 比农场 b b b 至少多种植了 c c c 个单位的作物;
  • 如果每行的第一个数是 2 2 2,接下来有三个整数 a , b , c a,b,c a,b,c,表示农场 a a a 比农场 b b b 至多多种植了 c c c 个单位的作物;
  • 如果每行的第一个数是 3 3 3,接下来有两个整数 a , b a,b a,b,表示农场 a a a 种植的的数量和 b b b 一样多。

输出格式

如果存在某种情况与小 K 的记忆吻合,输出 Yes,否则输出 No

样例 #1

样例输入 #1

3 3
3 1 2
1 1 3 1
2 2 3 2

样例输出 #1

Yes

提示

对于 100 % 100\% 100% 的数据,保证 1 ≤ n , m , a , b , c ≤ 5 × 1 0 3 1 \le n,m,a,b,c \le 5 \times 10^3 1n,m,a,b,c5×103

分析

差分约束模型,把每个都分析一下:

  1. 农场 a a a 比农场 b b b 至少多种植了 c c c 个单位的作物: x a − c ≥ x b x_a-c \ge x_b xacxb,构成(a,b,-c)
  2. 农场 a a a 比农场 b b b 至多多种植了 c c c 个单位的作物: x b + c ≥ x a x_b+c \ge x_a xb+cxa,构成(b,a,c)
  3. 农场 a a a 与农场 b b b 种植的作物数一样多: x a = x b → x a ≥ x b , x b ≥ x a x_a=x_b \to x_a \ge x_b,x_b \ge x_a xa=xbxaxb,xbxa,构成(a,b,0),(b,a,0)

代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e8+5,M=1e6;
vector<pair<int,int> > edges[M];
int dis[M];
int n,m,s;
int cnt[M];
bool inQueue[MAXN];
int q[MAXN],f=1,t=1;
void add(int u,int v,int w){edges[u].emplace_back(v,w);}
void read(){cin>>n>>m;for(int i=1,u,v,w,opt;i<=m;i++) {cin>>opt>>u>>v;if(opt<3) cin>>w;if(opt==1) add(u,v,-w);if(opt==2) add(v,u,w);if(opt==3) {add(u,v,0);add(v,u,0);} }
}
bool spfa(int s=0)
{memset(dis,0x3f,sizeof(dis));dis[s]=0;q[t++]=s;inQueue[s]=true;while(f<t){int x=q[f++];inQueue[x]=false;for(auto& edge:edges[x]){if(dis[edge.first]<=dis[x]+edge.second) continue;dis[edge.first]=dis[x]+edge.second;if(!inQueue[edge.first]){q[t++]=edge.first;inQueue[edge.first]=true;cnt[edge.first]++;if(cnt[edge.first]>=n+1) return false;}}}return true;
}
void solve(){for(int i=1;i<=n;i++) add(0,i,0);if(!spfa()) cout<<"No"; else cout<<"Yes";
}
int main()
{read();solve();return 0;
}

分析

1.超级源点
void solve(){for(int i=1;i<=n;i++) add(0,i,0);if(!spfa()) cout<<"No"; else cout<<"Yes";
}

差分约束需要超级源点,需要与每个点构成一条边,权值为0,因为spfa可以有效判断负环,if(cnt[edge.first]>=n+1) return false;需要注意,此处为n+1,因为有超级源点

2.效率问题

STL库中的queue效率低下,常数较高,在不开O2的前提下容易tle,推荐手打队:

  1. q.push(x) → \to q[tail++]=x;
  2. q.pop() → \to head++;
  3. q.top() → \to q[head]

相关文章:

P1993 小 K 的农场

小 K 的农场 题目描述 小 K 在 MC 里面建立很多很多的农场&#xff0c;总共 n n n 个&#xff0c;以至于他自己都忘记了每个农场中种植作物的具体数量了&#xff0c;他只记得一些含糊的信息&#xff08;共 m m m 个&#xff09;&#xff0c;以下列三种形式描述&#xff1a;…...

Spring boot 集成 Skywalking 配置 || Skywalking 打不开【已解决】

一、Skywalking官网 Apache SkyWalking 1.下载Skywalking APM &#xff08;如果下载最新的&#xff0c;双击打开闪退&#xff0c;选老点的版本&#xff09; 2. 下载 Skywalking Agents 如果下载太慢&#xff0c;建议复制下载链接&#xff0c;然后用下载器下载&#xff0c;比…...

手把手教你使用 ftrace 对 Linux 系统进行 debug

1、简介 strace:用来跟踪 Linux 进程执行时的系统调用和接收所接收的信号,可以跟踪到一个进程产生的系统调用,包括参数,返回值,执行消耗的时间。 ftrace:是一个 Linux 内核函数跟踪器,function tracer,旨在帮助开发人员和系统设计者可以找到内核内部发生的事情,从 L…...

【练】要求定义一个全局变量 char buf[] = “1234567“,创建两个线程,不考虑退出条件,打印buf

要求定义一个全局变量 char buf[] "1234567"&#xff0c;创建两个线程&#xff0c;不考虑退出条件&#xff0c;另&#xff1a; A线程循环打印buf字符串&#xff0c;B线程循环倒置buf字符串&#xff0c;即buf中本来存储1234567&#xff0c;倒置后buf中存储7654321. 不…...

iOS Viper架构(中文版)【看懂这篇就够了】

完整源码地址 一、iOS_Viper iOS的Viper架构&#xff0c;作为一个从业多年的iOS开发者&#xff0c;我个人认为应该要会一点viper 二、前言 viper的设计模式在iOS开发中不流行&#xff0c;甚至是Swift中&#xff0c;也没有用&#xff0c;我认为比较可惜。作为iOSer,当你掌握…...

深入理解缓存 TLB 原理

今天分享一篇TLB的好文章&#xff0c;希望大家夯实基本功&#xff0c;让我们一起深入理解计算机系统。 TLB 是 translation lookaside buffer 的简称。首先&#xff0c;我们知道 MMU 的作用是把虚拟地址转换成物理地址。 MMU工作原理 虚拟地址和物理地址的映射关系存储在页表…...

获取k8s scale资源对象的命令

kubectl get --raw /apis/<apiGroup>/<apiVersion>/namespaces/<namespaceName>/<resourceKind>/<resourceName>/scale 说明&#xff1a;scale资源对象用来水平扩展k8s资源对象的副本数&#xff0c;它是作为一种k8s资源对象的子资源存在&#xf…...

基于ChatYuan-large-v2 语言模型 Fine-tuning 微调训练 广告生成 任务

一、ChatYuan-large-v2 ChatYuan-large-v2是一个开源的支持中英双语的功能型对话语言大模型&#xff0c;与其他 LLM 不同的是模型十分轻量化&#xff0c;并且在轻量化的同时效果相对还不错&#xff0c;仅仅通过0.7B参数量就可以实现10B模型的基础效果&#xff0c;正是其如此的…...

SpringBoot集成Logback日志

SpringBoot集成Logback日志 文章目录 SpringBoot集成Logback日志一、什么是日志二、Logback简单介绍三、SpringBoot项目中使用Logback四、概念介绍一、日志记录器Logger1.1、日志记录器对象生成1.2、记录器的层级结构1.3、过滤器1.4、logger设置日志级别1.5、java代码演示1.6、…...

MATLAB(R2023a)添加工具箱TooLbox的方法-以GPOPS为例

一、找到工具箱存放位置 首先我们需要找到工具箱的存放位置&#xff0c;点击这个设置路径可以看到 我们的matlab工具箱的存放位置 C:\Program Files\MATLAB\R2023a\toolbox\matlab 从资源管理器中打开这个位置&#xff0c;可以看到里面各种工具箱 二、放入工具箱 解压我们…...

助力618-Y的混沌实践之路 | 京东云技术团队

一、写在前面 1、混沌是什么&#xff1f; 混沌工程&#xff08;Chaos Engineering&#xff09;的概念由 Netflix 在 2010 年提出&#xff0c;通过主动向系统中引入异常状态&#xff0c;并根据系统在各种压力下的行为表现确定优化策略&#xff0c;是保障系统稳定性的新型手段。…...

Python系统学习1-4-物理行、逻辑行、选择语句

一、行 (1) 物理行&#xff1a;程序员编写代码的行。 (2) 逻辑行&#xff1a;python解释器需要执行的指令。 (3) 建议&#xff1a; 一个逻辑行在一个物理行上。 如果一个物理行中使用多个逻辑行&#xff0c;需要使用分号&#xff1b;隔开。 (4) 换行&#xff1a; 如果…...

学习系统编程No.35【基于信号量的CP问题】

引言&#xff1a; 北京时间&#xff1a;2023/8/2/12:52&#xff0c;时间飞逝&#xff0c;恍惚间已经来到了八月&#xff0c;给我的第一感觉就是快开学了&#xff0c;别的感觉其实没有&#xff0c;哈哈&#xff01;看着身边的好友网络相关知识都要全部学完了&#xff0c;就好像…...

词嵌入、情感分类任务

目录 1.词嵌入&#xff08;word embedding&#xff09; 对单词使用one-hot编码的缺点是难以看出词与词之间的关系。 所以需要使用更加特征化的表示&#xff08;featurized representation&#xff09;&#xff0c;如下图所示&#xff0c;我们可以得到每个词的向量表达。 假设…...

TypeScript使用技巧

文章目录 使用技巧TypeScript内置的工具类型keyofextends 限定泛型interface 与 type 区别 TypeScript作为JavaScript的超集,通过提供静态类型系统和对ES6新特性的支持,使JavaScript开发变得更加高效和可维护。掌握TypeScript的使用技巧,可以帮助我们更好地开发和组织JavaScrip…...

MySQL — InnoDB事务

文章目录 事务定义事务特性事务隔离级别READ UNCOMMITTEDREPEATABLE READREAD COMMITTEDSERIALIZABLE 事务存在的问题脏读&#xff08;Dirty Read&#xff09;不可重复读&#xff08;Non-repeatable Read&#xff09;幻读&#xff08;Phantom Read&#xff09; 事务定义 数据库…...

LeetCode 42. 接雨水(动态规划 / 单调栈)

题目&#xff1a; 链接&#xff1a;LeetCode 42. 接雨水 难度&#xff1a;困难 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图&#xff0c;计算按此排列的柱子&#xff0c;下雨之后能接多少雨水。 示例 1&#xff1a; 输入&#xff1a;height [0,1,0,2,1,0,1,3,2,1,2…...

顺序表、链表刷题指南(力扣OJ)

目录 前言 题目一&#xff1a;删除有序数组中的重复项 思路&#xff1a; 题解&#xff1a; 题目二&#xff1a;合并两个有序数组 思路&#xff1a; 分析&#xff1a; 题解&#xff1a; 题目三&#xff1a;反转链表 思路&#xff1a; 分析&#xff1a; 题解&#xff1a; 题目四&…...

Lambda表达式总结

Lambda作为Java8的新特性&#xff0c;本篇文章主要想总结一下常用的一下用法和api 1.接口内默认方法实现 public interface Formula {double calculate(int a);// 默认方法default double sqrt(int a) {return Math.sqrt(a);} }public static void main(String[] args) {Form…...

岛屿的最大面积

给你一个大小为 m x n 的二进制矩阵 grid 。 岛屿 是由一些相邻的 1 (代表土地) 构成的组合&#xff0c;这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0&#xff08;代表水&#xff09;包围着。 岛屿的面积是岛上值为 1 …...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

C# 类和继承(抽象类)

抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

Android第十三次面试总结(四大 组件基础)

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...

Docker 本地安装 mysql 数据库

Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker &#xff1b;并安装。 基础操作不再赘述。 打开 macOS 终端&#xff0c;开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...

GitFlow 工作模式(详解)

今天再学项目的过程中遇到使用gitflow模式管理代码&#xff0c;因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存&#xff0c;无论是github还是gittee&#xff0c;都是一种基于git去保存代码的形式&#xff0c;这样保存代码…...