【AcWing】852. spfa判断负环

 

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;

const int N= 1e5+10;

int n,m;
int h[N],w[N],e[N],ne[N],idx;
int dist[N],cnt[N];//cnt存最短路径的边数
bool st[N];

void add(int a,int b,int c){
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;  
}

int spfa(){
    //不需要初始化,求的不是距离1号点的最短路径,而是是不是存在负环。
    //memset初始化作用于的是求起点到终点的最短路径,而判读负环只依靠dist[j]>dist[t]+w[i]递推就可以判断。
    //dist只是工具数组,初值是多少都无所谓,dist不断变小才是关键。
    //把所有顶点都入队了,可以看成所有点都是初始点。
    //在第一步每个点都作为初始点走下一步时,下一步如果是正权值,那压根就不会走,下一步是负权值才会走。由于负权回路总和是负数,所以就算下一步是正权值,由前几步积累的负值的绝对值肯定会大于这个值,然后加完为负数,就能走了。一直无限循环,直到积累的边数达到判断条件。

    /*memset(dist,0x3f,sizeof dist);
    dist[1]=0;*/
    
    queue<int> q;
    //不能把1号点放进去,题目判断是否存在负环,并不是判断是否存在从1开始的负环。就是可能存在1号点到不了的负环。
    //那怎么办呢?把每个点都放到初始的点集里面。这样只要存在负环的话,就一定可以找到。
    for(int i=1;i<=n;i++){
        q.push(i);
        st[i]=true;
    }
    
    while(q.size()){
        int t=q.front();
        q.pop();
        st[t]=false;
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(dist[j]>dist[t]+w[i]){
                dist[j]=dist[t]+w[i];
                cnt[j]=cnt[t]+1;
                
                if(cnt[j]>=n) return true;
                
                if(!st[j]){
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
    return false;
}

int main(){
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    
    if(spfa()) puts("Yes");
    else puts("No");
    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/873098.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

前端:Vue3学习-2

前端:Vue3学习-2 1. vue3 新特性-defineOptions2. vue3 新特性-defineModel3. vue3 Pinia-状态管理工具4. Pinia 持久化插件 -> pinia-plugin-persistedstate 1. vue3 新特性-defineOptions 如果要定义组件的name或其他自定义的属性&#xff0c;还是得回归原始得方法----再…

输送线相机拍照信号触发(博途PLC高速计数器中断立即输出应用)

博途PLC相关中断应用请参考下面文章链接: T法测速功能块 T法测速功能块(博途PLC上升沿中断应用)-CSDN博客文章浏览阅读165次。本文介绍了博途PLC中T法测速的原理和应用,包括如何开启上升沿中断、配置中断以及T法测速功能块的使用。重点讲述了在中断事件发生后执行的功能块处…

有希带你深入理解指针(4)

目录 前言&#x1f970;1.回调函数&#x1f63a;1.1回调函数的概念&#x1f60b; 2.qsort使用&#x1f92f;2.1什么是qsort&#x1f47b;2.2 qsort函数的使用&#x1f9d0; 3.模拟实现qsort&#x1f60e; 前言&#x1f970; 本篇文章是对指针知识的进一步讲解&#xff0c;如果…

【leetcode】二分查找专题

文章目录 1.基本的二分查找2.使用二分 查找左右端点2.1 左右端点2.2 二分模板 3.搜索插入位置4.x的平方根5.山脉数组的顶峰6.寻找峰值7.寻找旋转排序数组中的最小值 对于二分查找&#xff0c;相信大家都再熟悉不过了。一旦数据是有序的&#xff0c;我们大概率会想到二分&#x…

上海小学生古诗文大会2024年备考:吃透历年真题和知识点(持续)

一、小学生古诗文大会真题精选&#xff08;答案和解析见文末&#xff09; *1. 孟浩然的《宿建德江》是一首&#xff08;&#xff09;。 A.五言绝句 B.七言绝句 C.五言律诗 D.七言律诗 *2. 茕茕子立&#xff0c;形影相吊出自&#xff08;&#xff09; A.《出师表》 B.《…

常见Python GUI库分析

引言 在Python环境下进行桌面编程时&#xff0c;选择合适的GUI&#xff08;图形用户界面&#xff09;库至关重要。在Python环境下进行桌面编程GUI开发时&#xff0c;有多个优秀的库可供选择。以下是一些推荐的GUI库&#xff0c;包括它们的推荐理由、优劣势以及简单的demo示例。…

Deepspeed框架学习笔记

DeepSpeed 是由 Microsoft 开发的深度学习优化库,与PyTorch/TensorFlow等这种通用的深度学习框架不同的是,它是一个专门用于优化和加速大规模深度学习训练的工具,尤其是在处理大模型和分布式训练时表现出色。它不是一个独立的深度学习框架,而是依赖 PyTorch 等框架,扩展了…

C++20中lambda表达式新增加支持的features

1.弃用通过[]隐式捕获this&#xff0c;应使用[,this]或[,*this]显示捕获&#xff1a; namespace { struct Foo {int x{ 1 };void print(){//auto change1 [] { // badauto change1 [, this] { // good, this: referencethis->x 11;};change1();std::cout << "…

麒麟系统安装GPU驱动

1.nvidia 1.1显卡驱动 本机显卡型号:nvidia rtx 3090 1.1.1下载驱动 打开 https://www.nvidia.cn/geforce/drivers/ 也可以直接使用下面这个地址下载 https://www.nvidia.com/download/driverResults.aspx/205464/en-us/ 1.1.3安装驱动 右击&#xff0c;为run文件添加可…

【YOLO 系列】基于YOLOV8的智能花卉分类检测系统【python源码+Pyqt5界面+数据集+训练代码】

前言&#xff1a; 花朵作为自然界中的重要组成部分&#xff0c;不仅在生态学上具有重要意义&#xff0c;也在园艺、农业以及艺术领域中占有一席之地。随着图像识别技术的发展&#xff0c;自动化的花朵分类对于植物研究、生物多样性保护以及园艺爱好者来说变得越发重要。为了提…

接口自动化三大经典难题

目录 一、接口项目不生成token怎么解决关联问题 1. Session机制 2. 基于IP或设备ID的绑定 3. 使用OAuth或第三方认证 4. 利用隐式传递的参数 5. 基于时间戳的签名验证 二、接口测试中网络问题导致无法通过怎么办 1. 重试机制 2. 设置超时时间 3. 使用模拟数据 4. 网…

【STM32开发】GPIO最全解析及应用实例

目录 【1】GPIO概述 GPIO的基本概念 GPIO的应用 【2】GPIO功能描述 1.IO功能框图 2.知识补充 3.功能详述 浮空输入 上拉输入 下拉输入 模拟输入 推挽输出 开漏输出 复用开漏输出和复用推挽输出 【3】GPIO常用寄存器 相关寄存器介绍 4个32位配置寄存器 2个32位数据寄存器 1个32位…

Android的logcat日志详解

Android log系统 logcat介绍 logcat是android中的一个命令行工具&#xff0c;可以用于得到程序的log信息。下面介绍 adb logcat中的详细参数命令以及如何才能高效的打印日志&#xff0c;或把日志保存到我们指定的位置。 可以输入 adb logcat --help&#xff0c;查看一下一些简…

深入CSS 布局——WEB开发系列29

CSS 页面布局技术允许我们拾取网页中的元素&#xff0c;并且控制它们相对正常布局流、周边元素、父容器或者主视口/窗口的位置。 一、正常布局流&#xff08;Normal Flow&#xff09; CSS的布局基础是“正常流”&#xff0c;也就是页面元素在没有特别指定布局方式时的默认排列…

图神经网络(2)预备知识

1. 图的基本概念 对于接触过数据结构和算法的读者来说&#xff0c;图并不是一个陌生的概念。一个图由一些顶点也称为节点和连接这些顶点的边组成。给定一个图G(V,E), 其 中V{V1,V2,…,Vn} 是一个具有 n 个顶点的集合。 1.1邻接矩阵 我们用邻接矩阵A∈Rnn表示顶点之间的连接关…

AI自动生成PPT哪个软件好?如何自动生成专业级PPT?

新学期伊始&#xff0c;准备开学演讲稿的你是否还在为制作PPT而烦恼&#xff1f;别担心&#xff0c;现在有了AI的帮助&#xff0c;生成专业且吸引人的PPT变得轻而易举。 本文将为你揭秘4种高效的AI自动生成PPT的方法&#xff0c;让你在新学期的演讲中脱颖而出。无论是简洁明了…

数据权限的设计与实现系列6——前端筛选器组件Everright-filter使用探索

linear 功能探索 最终我们是需要使用 API 的方式&#xff0c;调用后端服务拉取数据填充筛选器组件&#xff0c;不过在探索阶段&#xff0c;直接用 API 方式&#xff0c;就需要构造 mock 数据&#xff0c;比较麻烦&#xff0c;因此先使用 Function 方式来进行功能验证。 组件初…

Visual Studio Code:让你的工作效率飞升的秘密武器

在现代软件开发环境中&#xff0c;效率已成为每个开发者追求的目标。而在众多编程工具中&#xff0c;Visual Studio Code&#xff08;简称VS Code&#xff09;凭借其强大的功能、轻量的界面和高度的可定制性&#xff0c;成为了全球开发者的首选。无论你是编写前端代码、后端服务…

软考(计算机技术与软件专业技术资格(水平)考试)

天行健&#xff0c;君子以自强不息&#xff1b;地势坤&#xff0c;君子以厚德载物。 每个人都有惰性&#xff0c;但不断学习是好好生活的根本&#xff0c;共勉&#xff01; 文章均为学习整理笔记&#xff0c;分享记录为主&#xff0c;如有错误请指正&#xff0c;共同学习进步。…

SpringBoot教程(十五) | SpringBoot集成RabbitMq(消息丢失、消息重复、消息顺序、消息顺序)

SpringBoot教程&#xff08;十五&#xff09; | SpringBoot集成RabbitMq&#xff08;消息丢失、消息重复、消息顺序、消息顺序&#xff09; RabbitMQ常见问题解决方案问题一&#xff1a;消息丢失的解决方案&#xff08;1&#xff09;生成者丢失消息丢失的情景解决方案1&#xf…