当前位置: 首页 > 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 …...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘

美国西海岸的夏天&#xff0c;再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至&#xff0c;这不仅是开发者的盛宴&#xff0c;更是全球数亿苹果用户翘首以盼的科技春晚。今年&#xff0c;苹果依旧为我们带来了全家桶式的系统更新&#xff0c;包括 iOS 26、iPadOS 26…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

GitHub 趋势日报 (2025年06月08日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

Spring AI 入门:Java 开发者的生成式 AI 实践之路

一、Spring AI 简介 在人工智能技术快速迭代的今天&#xff0c;Spring AI 作为 Spring 生态系统的新生力量&#xff0c;正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务&#xff08;如 OpenAI、Anthropic&#xff09;的无缝对接&…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...

【JVM】Java虚拟机(二)——垃圾回收

目录 一、如何判断对象可以回收 &#xff08;一&#xff09;引用计数法 &#xff08;二&#xff09;可达性分析算法 二、垃圾回收算法 &#xff08;一&#xff09;标记清除 &#xff08;二&#xff09;标记整理 &#xff08;三&#xff09;复制 &#xff08;四&#xff…...

【LeetCode】算法详解#6 ---除自身以外数组的乘积

1.题目介绍 给定一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O…...

tauri项目,如何在rust端读取电脑环境变量

如果想在前端通过调用来获取环境变量的值&#xff0c;可以通过标准的依赖&#xff1a; std::env::var(name).ok() 想在前端通过调用来获取&#xff0c;可以写一个command函数&#xff1a; #[tauri::command] pub fn get_env_var(name: String) -> Result<String, Stri…...