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

P3385 【模板】负环

P3385 【模板】负环 - 洛谷

题目描述

给定一个 n 个点的有向图,请求出图中是否存在从顶点 1 出发能到达的负环。

负环的定义是:一条边权之和为负数的回路。

输入格式

本题单测试点有多组测试数据。

输入的第一行是一个整数 T,表示测试数据的组数。对于每组数据的格式如下:

第一行有两个整数,分别表示图的点数 n 和接下来给出边信息的条数 m。

接下来 m 行,每行三个整数 u,v,w。

  • 若 w>0,则表示存在一条从 u 至 v 边权为 w 的边,还存在一条从 v 至 u 边权为 w 的边。
  • 若 w<0,则只表示存在一条从 u 至 v 边权为 w 的边。

输出格式

对于每组数据,输出一行一个字符串,若所求负环存在,则输出 YES,否则输出 NO

输入输出样例

输入 #1

2
3 4
1 2 2
1 3 4
2 3 1
3 1 -3
2 3
1 2 3
2 3 4
3 1 -8

输出 #1

NO
YES

说明/提示

数据规模与约定

对于全部的测试点,保证:

  • 1≤n≤2×103
  • 1≤m≤3×103
  • 1≤u,v≤n
  • −104≤w≤104
  • 1≤T≤10

提示

请注意,m 不是图的边数。

思路:

SPFA算法原理

SPFA算法是Bellman-Ford算法的队列优化版本,用于求解单源最短路径问题,特别适用于存在负权边的图。算法的基本思想是:

  1. 初始化:将源点到所有点的最短路径估计值初始化为无穷大(或一个很大的数),源点到自身的距离初始化为0,并将源点加入队列。
  2. 松弛操作:每次从队列中取出一个点,对该点的所有邻接点进行松弛操作。如果通过当前点能够找到更短的路径到达邻接点,则更新邻接点的最短路径估计值,并将邻接点加入队列(如果它不在队列中)。
  3. 重复执行:不断重复上述松弛操作,直到队列为空。

负环的性质

负环是指图中存在一个环,环上的边权之和为负数。负环的存在会导致最短路径问题无解,因为可以无限次地通过负环来减小路径长度。

SPFA判断负环的原理

在SPFA算法中,如果图中存在负环,那么算法在松弛操作时会不断地更新负环上点的最短路径估计值,并将这些点反复加入队列。具体来说,如果一个点被松弛了多次(超过图中节点的总数),说明该点可能位于一个负环上,因为正常情况下,从一个点到另一个点的最短路径不会经过超过图中节点总数的边数(在最短路径中,每个节点最多被经过一次,除非存在环)。

为了检测负环,SPFA算法在执行过程中会记录每个点进入队列的次数。如果一个点进入队列的次数超过了图中节点的总数,就可以判定图中存在负环。

算法实现细节

在实际实现中,SPFA算法通常使用一个计数器数组来记录每个点进入队列的次数。在松弛操作时,如果更新了某个点的最短路径估计值,并且该点不在队列中,就将其加入队列,并增加其计数器值。最后,检查所有点的计数器值,如果存在超过图中节点总数的计数器值,就返回存在负环的结果。

代码如下:

#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <cstring>
using namespace std;
typedef long long ll;
const ll N = 2e5 * 5 + 5;
ll tot = 0;
ll n, m, s;
struct Edge{ll next,to,w;
}e[N];
ll head[N],dis[N]; 
void add(ll u,ll v,ll w)
{tot++;e[tot].next = head[u];e[tot].to = v;e[tot].w = w;head[u] = tot;
}
void spfa()
{queue<ll> q;q.push(s);memset(dis,0x3f,sizeof dis);dis[s]=0;while(!q.empty()){ll pos = q.front();q.pop();ll u = head[u];while(u != -1){ll to = e[u].to;ll w = e[u].w;if(dis[to] > w + dis[pos]){dis[to] = w + dis[pos];q.push(to);}}}
}
int main()
{cin >> n >> m >> s;for(ll i = 1 ; i <= m ; i++){ll u,v,w;cin >> u >> v >> w;add(u,v,w);}spfa();return 0;
}

相关文章:

P3385 【模板】负环

P3385 【模板】负环 - 洛谷 题目描述 给定一个 n 个点的有向图&#xff0c;请求出图中是否存在从顶点 1 出发能到达的负环。 负环的定义是&#xff1a;一条边权之和为负数的回路。 输入格式 本题单测试点有多组测试数据。 输入的第一行是一个整数 T&#xff0c;表示测试数…...

破解透明物体抓取难题,地瓜机器人CASIA 推出几何和语义融合的单目抓取方案|ICRA 2025

概述 近日&#xff0c;全球机器人领域顶会ICRA 2025&#xff08;IEEE机器人与自动化国际会议&#xff09;公布论文录用结果&#xff0c;地瓜机器人主导研发的DOSOD开放词汇目标检测算法与MODEST单目透明物体抓取算法成功入选。前者通过动态语义理解框架提升复杂场景识别准确率…...

深度学习编译器(整理某survey)

一、深度学习框架 TensorFlow PyTorch MXNet ONNX:定义了一个统一的表示&#xff0c;DL models的格式方便不同框架之间的转换模型 二、深度学习硬件 通用硬件&#xff08;CPU、GPU&#xff09;&#xff1a;通过硬件和软件优化支持深度学习工作负载 GPU:通过多核架构实现高…...

【计算机网络入门】应用层

目录 1.网络应用模型 1.1 C/S模型&#xff08;客户端服务器模型&#xff09; 1.2 P2P模型&#xff08;对等模型&#xff09; 2. DNS系统 2.1 域名 2.2 域名解析流程 3. FTP文件传输协议 4. 电子邮件系统 4.1 SMTP协议 4.2 pop3协议 4.3 IMAP协议 4.4 基于万维网的电…...

@PostConstruct注解的作用

PostConstruct 注解功能是在一个类的所有依赖被注入完成后&#xff0c;才会被执行的方法。这种方法通常用于类的初始化&#xff0c;初始化过程中可以进行一些资源加载、连接建立、或其他必要的配置工作。PostConstruct 方法仅被调用一次&#xff0c;通常修饰符是public或者prot…...

HTML + CSS 题目

1.说说你对盒子模型的理解? 一、是什么 对一个文档进行布局的时候&#xff0c;浏览器渲染引擎会根据标准之一的css基础盒模型&#xff0c;将所有元素表示为一个个矩形的盒子。 一个盒子由四个部分组成: content&#xff0c;padding&#xff0c;border&#xff0c;margin 下…...

通过多线程获取RV1126的AAC码流

目录 一RV1126多线程获取音频编码AAC码流的流程 1.1AI模块的初始化并使能 1.2AENC模块的初始化 ​​​​​​​1.3绑定AI模块和AENC模块 ​​​​​​​1.4多线程获取每一帧AAC码流 ​​​​​​​1.5每个AAC码流添加ADTSHeader头部 ​​​​​​​1.6写入具体每一帧AAC的…...

sql sqlserver的进程资源查看,杀掉多余进程

主要是由三个表组成 sys.sysprocesses、sys.dm_exec_sessions、sys.dm_exec_requests 后面两个在2008版本后使用&#xff0c;主要使用sys.dm_exec_sessions SELECT spid AS 会话ID, -- 进程&#xff08;会话&#xff09;的ID blocked AS 被阻塞的会话…...

自然语言处理:朴素贝叶斯

介绍 大家好&#xff0c;博主又来和大家分享自然语言处理领域的知识了。按照博主的分享规划&#xff0c;本次分享的核心主题本应是自然语言处理中的文本分类。然而&#xff0c;在对分享内容进行细致梳理时&#xff0c;我察觉到其中包含几个至关重要的知识点&#xff0c;即朴素…...

Pytorch实现之LSRGAN,轻量化SRGAN超分辨率SAR

简介 简介:在SRGAN的基础上设计了一个轻量化的SRGAN模型结构,通过DSConv+CA与残差结构的设计来减少参数量,同时利用SeLU激活函数构造。与多类SRGAN改进不同的是,很少使用BN层。 论文题目:Lightweight Super-Resolution Generative Adversarial Network for SAR Images(…...

学习记录-缺陷

目录 一、缺陷的判定标准 二、缺陷产生的原因 三、缺陷的生存周期 四、软件缺陷描述及提交要素 1.缺陷的核心内容 2.缺陷的提交要素 五、软件缺陷类型 一、缺陷的判定标准 二、缺陷产生的原因 三、缺陷的生存周期 注入bug > 发现bug > 清除bug 四、软件缺陷描述及提…...

文件压缩与解压工具7-Zip的安装和使用(免费)

一.介绍 7-Zip 是一款开源的文件压缩与解压缩工具&#xff0c;支持多种压缩格式&#xff0c;如 7z、ZIP、RAR、TAR 等。它具有高压缩比&#xff0c;尤其是其独有的 7z 格式&#xff0c;并集成了文件管理器。7-Zip 适用于 Windows 系统&#xff0c;提供命令行版本&#xff0c;…...

如何实现对用户密码的加密

摘要算法&#xff1a; 同样的明文&#xff0c;经过同样的摘要算法&#xff0c;得到的结果是一样的 验证方法&#xff1a;验证经过摘要算法处理后的结果&#xff0c;如果密文一样那么就认为明文是一样的 //数据库存储的一定是密文&#xff0c;用户输入的是明文&#xff1b;把…...

MySQL基础四(JDBC)

JDBC(重点) 数据库驱动 程序会通过数据库驱动&#xff0c;和数据库打交道。 sun公司为了简化开发人员对数据库的统一操作&#xff0c;提供了一个Java操作数据库的规范。这个规范由具体的厂商去完成。对应开发人员来说&#xff0c;只需要掌握JDBC接口。 熟悉java.sql与javax.s…...

审批流AntV框架蚂蚁数据可视化X6饼图(注释详尽)

大家好&#xff0c;这次使用的是AntV的蚂蚁数据可视化X6框架&#xff0c;类似于审批流的场景等&#xff0c;代码如下&#xff1a; X6框架参考网址&#xff1a;https://x6.antv.vision/zh/examples/showcase/practices#bpmn 可以进入该网址&#xff0c;直接复制下方代码进行调试…...

用Python之requests库调用大模型API实现多轮对话

文章目录 1. 多轮对话实现概述2. 多轮对话全上下文实现3. 多轮对话最近上下文的链式实现4. 总结 1. 多轮对话实现概述 多轮对话功能可以让大模型“拥有记忆”&#xff0c;满足如追问、信息采集等需要连续交流的场景。 AI大模型API 不会记录您的对话历史记录。如果您需要让大模…...

《异步江湖:XHR、Promise 与 Event Loop 的恩怨情仇》

XMLHttpRequest XMLHttpRequest&#xff08;简称 XHR&#xff09;是浏览器提供的一个 JavaScript 对象&#xff0c;用于在客户端和服务器之间发送 HTTP 请求。它是实现 AJAX&#xff08;Asynchronous JavaScript and XML&#xff09; 技术的核心工具&#xff0c;允许网页在不…...

【极客时间】浏览器工作原理与实践-2 宏观视角下的浏览器 (6讲) - 2.5 渲染流程(上):HTML、CSS和JavaScript,是如何变成页面的?

https://time.geekbang.org/column/article/118205 2.5 渲染流程&#xff08;上&#xff09;&#xff1a;HTML、CSS和JavaScript&#xff0c;是如何变成页面的&#xff1f; 2.4讲了导航相关的流程&#xff0c;那导航被提交后又会怎么样呢&#xff1f; 就进入了渲染阶段。 这…...

蓝桥杯第15届真题解析

由硬件框图可以知道我们要配置LED 和按键、lcd&#xff0c;解决lcd引脚冲突 LED 先配置LED的八个引脚为GPIO_OutPut&#xff0c;锁存器PD2也是&#xff0c;然后都设置为起始高电平&#xff0c;生成代码时还要去解决引脚冲突问题 按键 按键配置&#xff0c;由原理图按键所对引…...

19c rac-expdp备份异常处理

客户反馈&#xff0c;有套19c rac环境&#xff0c;补丁是19.13的&#xff0c;有1个节点使用expdp备份用户异常&#xff0c;报错如下 Connected to: Oracle Database 19c Enterprise Edition Release 19.0.0.0.0 - Production ORA-31626: job does not exist ORA-31637: cannot…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中&#xff0c;新增了一个本地验证码接口 /code&#xff0c;使用函数式路由&#xff08;RouterFunction&#xff09;和 Hutool 的 Circle…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...

Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐&#xff1a;「storms…...

django blank 与 null的区别

1.blank blank控制表单验证时是否允许字段为空 2.null null控制数据库层面是否为空 但是&#xff0c;要注意以下几点&#xff1a; Django的表单验证与null无关&#xff1a;null参数控制的是数据库层面字段是否可以为NULL&#xff0c;而blank参数控制的是Django表单验证时字…...

Linux系统部署KES

1、安装准备 1.版本说明V008R006C009B0014 V008&#xff1a;是version产品的大版本。 R006&#xff1a;是release产品特性版本。 C009&#xff1a;是通用版 B0014&#xff1a;是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存&#xff1a;1GB 以上 硬盘&#xf…...

Leetcode33( 搜索旋转排序数组)

题目表述 整数数组 nums 按升序排列&#xff0c;数组中的值 互不相同 。 在传递给函数之前&#xff0c;nums 在预先未知的某个下标 k&#xff08;0 < k < nums.length&#xff09;上进行了 旋转&#xff0c;使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...