算法基础之SPFA判断负环

SPFA判断负环

  • 核心思想:spfa算法 当遍历一个点时 cnt数组记录边数 若有负环 边数会无限+1 cnt>=n是即为有负环

    •   #include<iostream>
        #include<cstring>
        #include<algorithm>
        #include<queue>
        
        using namespace std;
        const int N = 2010 , M = 10010;
        
        int h[N], e[M] , ne[M] , w[M] , idx;
        int d[M] , cnt[N];
        int n,m;
        bool st[N];
        
        void add(int a,int b,int c)
        {
            e[idx] = b;
            ne[idx] = h[a];
            w[idx] = c;
            h[a] = idx++;
        }
        
        bool spfa()
        {
            //不用初始化d,只要确定d更新了即可
            queue<int> q;  
            for(int i=1;i<=n;i++)
            {
                st[i] = true;
                q.push(i);  //把每个点都放进去 因为不一定是从1开始的回路 可能是从2开始的不全是负值的环
                //如果不放:只能求出从1开始的负环
            }
            
            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(d[j] > d[t] + w[i])
                    {
                        d[j] = d[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);
            while(m--)
            {
                int a,b,c;
                cin>>a>>b>>c;
                add(a,b,c);
            }
            
            if(spfa()) puts("Yes");
            else puts("No");
            
        }
      

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

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

相关文章

天猫数据分析-天猫查数据软件-11月天猫平台饮料市场品牌及店铺销量销额数据分析

今年以来&#xff0c;饮料是快消品行业中少数保持稳定增长的品类之一。 11月份&#xff0c;饮料市场同样呈现较好的增长态势。根据鲸参谋电商数据分析平台的相关数据显示&#xff0c;今年11月份&#xff0c;天猫平台上饮料市场的销量为2700万&#xff0c;环比增长约42%&#xf…

数据结构:图文详解 队列 | 循环队列 的各种操作(出队,入队,获取队列元素,判断队列状态)

目录 队列的概念 队列的数据结构 队列的实现 入队 出队 获取队头元素 获取队列长度 循环队列的概念 循环队列的数据结构 循环队列的实现 判断队列是否为空 判断队列是否已满 入队 出队 得到队头元素 得到队尾元素 队列的概念 队列&#xff08;Queue&#xff0…

【网络安全】-Linux操作系统—VMWare软件

文章目录 VMWare软件的安装选择VMWare版本下载VMWare安装过程 VMWare的常用操作创建新的虚拟机配置虚拟机启动和关闭虚拟机安装VMWare Tools VMWare的克隆和快照克隆&#xff08;Clone&#xff09;快照&#xff08;Snapshot&#xff09; 总结 VMWare是一种流行的虚拟化软件&…

物联网对接使用蓝牙还是WiFi,应该如何选择?

蓝牙是一种无线技术协议&#xff0c;可促进连接设备之间短距离的数据交换。它依赖于物理邻近性并使用2.400至2.485 GHz之间的UHF&#xff08;超高频&#xff09;无线电波。蓝牙旨在创建个人区域网络&#xff08;PAN&#xff09;并在笔记本电脑、智能手机和外围设备等计算设备之…

webview 的 title 和 url

在Appium以混合型App进行自动化操作时&#xff0c;遇到WebView时切换至WebView才能进行操作。当遇到多个WebView时&#xff0c;可以利用 title 和 url 切换至相应的 WebView。

✺ch5——纹理贴图

目录 加载纹理图像文件纹理坐标在着色器中使用纹理&#xff1a;采样器变量和纹理单元纹理贴图&#xff1a;示例程序多级渐远纹理贴图各向异性过滤环绕和平铺透视变形材质——更多OpenGL细节补充说明 纹理贴图是在栅格化的模型表面上覆盖图像的技术。 它是为渲染场景添加真实感的…

宏基因组学Metagenome-磷循环Pcycle功能基因分析-从分析过程到代码及结果演示-超详细保姆级流程

大背景介绍 生信分析,凡事先看论文,有了论文就有了参考,后续分析就有底了,直接上硬菜开干: PCycDB: a comprehensive and accurate database for fast analysis of phosphorus cycling genes - PubMed 数据库及部分分析代码github库: GitHub - ZengJiaxiong/Phospho…

docker 与 ffmpeg

创建容器 docker run -it -v /mnt/f/ffmpeg:/mnt/f/ffmpeg --name ffmpeg 49a981f2b85f /bin/bash 在 Linux 上编译 FFmpeg&#xff1a; 安装依赖库&#xff1a; sudo apt-get update sudo apt-get install build-essential yasm cmake libtool libc6 libc6-dev unzip wget下…

SpringCloud-高级篇(八)

&#xff08;1&#xff09;TCC模式 前面学了XA和AT模式&#xff0c;这两种模式最终都能实现一致性&#xff0c;和隔离性&#xff0c;XA是强一致&#xff0c;AT是最终一致&#xff0c;隔离性呢XA是在第一阶段不提交&#xff0c;基于事务本身的特性来完成隔离&#xff0c;AT则是…

Python都有什么特性,为什么适合每个人学习?详细解读来了

Python编程语言简介 Python&#xff0c;一种高层次的、解释型的编程语言&#xff0c;以其跨平台性、易读性和灵活性在全球编程界占据了重要的地位。自1991年首次发布以来&#xff0c;Python已经成为了无数程序员和企业的首选语言&#xff0c;尤其是在快速开发和原型设计方面。 …

Ansible:模块1

Ansible&#xff1a; 远程操作主机功能 自动化运维&#xff08;playbook 剧本 yaml&#xff09; 是基于python开发的配置管理和应用部署工具。在自动化运维中&#xff0c;现在是一军突起。 Ansible能批量配置&#xff0c;部署&#xff0c;管理上千台主机。类似于xshell的一…

MFC 程序执行流程

目录 MFC 程序启动 MFC 入口函数 程序执行流程总结 在Win32课程中WinMain由程序员自己实现&#xff0c;那么流程是程序员安排&#xff0c;但到了MFC中&#xff0c;由于MFC库实现WinMain&#xff0c;也就意味着MFC负责安排程序的流程。 MFC 程序启动 程序的启动&#xff0c;…

红枣期货个股(红枣期货个股:投资方向分析)

红枣期货个股介绍 红枣是我国传统的绿色健康食品&#xff0c;具有营养丰富、味道独特的特点&#xff0c;深受消费者喜爱。红枣产业链较长&#xff0c;包括种植、采摘、加工、销售等环节&#xff0c;其中期货是红枣产业不可或缺的一环。红枣期货个股作为期货交易市场上的重要投…

mybatis中oracle的sql没走索引导致特别慢(未加jdbcType的)

如果直接跑sql是能走索引很快&#xff0c;在mybatis中不能&#xff0c;可能就是jdbcType的原因。 比如&#xff0c;我有一个属性A&#xff0c;在表里面是VARCHAR2类型&#xff0c;但是在mybatis中的sql是#{a}&#xff0c;缺少jdbcTypeJdbcType.VARCHAR&#xff0c;就会导致myba…

risc-v system instruction

ECALL ecall 指令以前叫做 scall&#xff0c;用于执行环境的变更&#xff0c;它会根据当前所处模式触发不同的执行环境切换异常, 用来执行需要更高权限才能执行的功能;简单来说&#xff0c;ecall 指令将权限提升到内核模式并将程序跳转到指定的地址。操作系统内核和应用程序其实…

AD采集卡设计方案:630-基于PCIe的高速模拟AD采集卡

基于PCIe的高速模拟AD采集卡 一、产品概述 基于PCIe的一款分布式高速数据采集系统&#xff0c;实现多路AD的数据采集&#xff0c;并通过PCIe传输到存储计算服务器&#xff0c;实现信号的分析、存储。 北京太速科技&#xff0c;产品固化FPGA逻辑&#xff0c;适配2路…

ShardingSphere-JDBC 和 ShardingSphere-Proxy,你选择哪一个

参考文章 总结&#xff1a; 只使用Java&#xff0c;ShardingSphere-JDBC更好有异构语言的话&#xff0c;ShardingSphere-Proxy 更好混用也挺香

Flink系列之:监控Checkpoint

Flink系列之&#xff1a;监控Checkpoint 一、概览二、概览&#xff08;Overview&#xff09;选项卡三、历史记录&#xff08;History&#xff09;选项卡四、历史记录数量配置五、摘要信息&#xff08;Summary&#xff09;选项卡六、配置信息&#xff08;Configuration&#xff…

100GPTS计划-AI动漫AnimeArtisan

地址 https://poe.com/AnimeArtisan https://chat.openai.com/g/g-LM6ObVhfF-anime-artisan 测试 风景类: 阳光、蓝天、白云、大海、海滩、森林、瀑布、山峰、雪山 日常类: 睡觉、跑步、学习、工作、做家务、看书、听音乐、运动、购物、煮饭 人物类: 女孩、男孩、老人、儿童…

『 Linux 』重新理解挂起状态

文章目录 &#x1f984; 前言新建状态 &#x1f40b;挂起状态 &#x1f40b;唤入唤出 &#x1f40b;进程与操作系统间的联系 &#x1f40b; &#x1f984; 前言 『 Linux 』使用fork函数创建进程与进程状态的查看中提到了对挂起状态的一个理解&#xff1b; ​ 挂起状态相比于其…
最新文章