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

算法基础之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");}
      

相关文章:

算法基础之SPFA判断负环

SPFA判断负环 核心思想&#xff1a;spfa算法 当遍历一个点时 cnt数组记录边数 若有负环 边数会无限1 cnt>n是即为有负环 #include<iostream>#include<cstring>#include<algorithm>#include<queue>using namespace std;const int N 2010 , M 10010…...

一些常用的Linux命令及其简要说明(持续更新)

1. cd&#xff1a;改变当前工作目录。 cd [directory]#例如 cd /home/user 2. ls&#xff1a;列出目录内容。 ls [-options] [file/directory]#例如 ls -l, ls /etc 3. pwd&#xff1a;显示当前工作目录。 pwd 4. mkdir&#xff1a;创建新目录。 mkdir [directory]#例…...

开发企业展示小程序的关键步骤和技巧

随着移动互联网的快速发展&#xff0c;小程序已经成为企业展示形象、推广产品和服务的重要工具。拥有一个优秀的小程序可以帮助企业提高品牌知名度&#xff0c;吸引更多潜在客户&#xff0c;提升用户体验。以下是拥有一个展示小程序的步骤&#xff1a; 确定需求和目标 首先&am…...

Python-Selenium-使用 pywinauto 实现 Input 上传文件

当前环境&#xff1a;Win10 Python3.7 pywinauto0.6.8&#xff0c;selenium3.14.1 示例代码 from pywinauto import Desktop import osapp Desktop() dialog app[打开] dialog[Edit].set_edit_text(os.getcwd() .\\example-01.jpg) dialog[Button].click() 其他方法&…...

Go语言运行时与自家平台对比后认识

引子 以前就了解Go语言&#xff0c;因为其天生为并发、并行而生&#xff0c;且在语言层面就进行了内秉设计。 总想对比于我们自研的分布式并发、并行平台&#xff0c;以利于得到一些新认识 &#xff1a;&#xff09; Go官网资料 在Go的官网资料提供了很好的资料和知识库 初…...

leetcode 450. 删除二叉搜索树中的节点

leetcode 450. 删除二叉搜索树中的节点 题目 给定一个二叉搜索树的根节点 root 和一个值 key&#xff0c;删除二叉搜索树中的 key 对应的节点&#xff0c;并保证二叉搜索树的性质不变。返回二叉搜索树&#xff08;有可能被更新&#xff09;的根节点的引用。 一般来说&#x…...

小红书可观测 Metrics 架构演进,如何实现数十倍性能提升?

在当前云原生时代&#xff0c;随着微服务架构的广泛应用&#xff0c;云原生可观测性概念被广泛讨论。可观测技术建设&#xff0c;将有助于跟踪、了解和诊断生产环境问题&#xff0c;辅助开发和运维人员快速发现、定位和解决问题&#xff0c;支撑风险追溯、经验沉淀、故障预警&a…...

selenium学习

前期准备 pip install selenium 获取浏览器驱动 我使用的浏览器是Chrome&#xff0c;所以这里只介绍关于Chrome获取浏览器驱动的方法&#xff1a; 需要注意的是&#xff1a;selenium 4.x 对之前版本的部分API调用方式进行了调整&#xff0c;这里就包括关于浏览器获取驱动的方式…...

前端开发新趋势:Web3、区块链和虚拟现实

目录 前言 Web3&#xff1a;下一代互联网 区块链技术 去中心化应用程序&#xff08;DApps&#xff09; 区块链&#xff1a;重塑数字世界 数字钱包 NFT&#xff08;非同质化代币&#xff09; 虚拟现实&#xff1a;沉浸式体验 WebVR和WebXR 三维图形 新挑战与机会 性…...

如何安装运行Wagtail并结合cpolar内网穿透实现公网访问网站界面

文章目录 前言1. 安装并运行Wagtail1.1 创建并激活虚拟环境 2. 安装cpolar内网穿透工具3. 实现Wagtail公网访问4. 固定的Wagtail公网地址 前言 Wagtail是一个用Python编写的开源CMS&#xff0c;建立在Django Web框架上。Wagtail 是一个基于 Django 的开源内容管理系统&#xf…...

【>D:\10\Debug\RCa00828(34): fatal error RC1022: expected ‘#endif‘】

1>D:\10\Debug\RCa00828(34): fatal error RC1022: expected ‘#endif’ The error message you’re seeing, fatal error RC1022: expected ‘#endif’, indicates that the resource compiler encountered an issue when processing a resource script file (typically w…...

使用vite搭建项目时,在启动vite后,浏览器显示页面:找不到localhost的网页

现象 在使用前端工具vite&#xff08;版本5&#xff09;&#xff0c;搭建vue3项目时&#xff0c;启动vite&#xff0c;浏览器显示页面&#xff1a;找不到localhost的网页, 起初怀疑是 未加参数 --host0.0.0.0,导致&#xff0c;后加上该参数后问题依旧 解决 将index.html页面…...

libp2p 快速开始

文章目录 第一部分&#xff1a;libp2p 快速入门一、什么是libp2plibp2p 发展历程libp2p的特性p2p 网络和我们熟悉的 client/server 网络的区别&#xff1a; 二、Libp2p的实现目标三、Libp2p的用途四、运行 Libp2p 协议流程libp2p 分为三层libp2p 还有一个局域网节点发现协议 mD…...

【数据结构】——排序算法简答题模板

目录 一、内排序和外排序二、排序算法的稳定性三、插入排序&#xff08;一&#xff09;直接插入排序的步骤&#xff08;二&#xff09;直接插入排序的稳定性&#xff08;三&#xff09;折半插入排序的步骤&#xff08;四&#xff09;希尔排序的步骤 四、交换排序&#xff08;一…...

vue3.0基础

1. setup函数 vue单页面使用到的变量和方法都定义在setup函数中,return后才能被页面引用 export default {setup(){const name 张三const person {name,age:30}function goWork(){consle.log(工作)}return {name,person,goWork}} } 注意&#xff1a;直接定义的变量修改不会…...

Kafka本地安装⭐️(Windows)并测试生产消息以及消费消息的可用性

2023.12.17 天气晴 温度较低 十点半&#xff0c;不是不想起实在是阳光浴太nice了日常三连&#xff0c;喂&#xff0c;刷&#xff0c;肝刷会儿博客&#xff0c;看会儿设计模式冷冷冷 进被窝 刷视频 睡觉看看kafka的本地部署 》》实践》》成功写会儿博客&#xff0c…...

生产环境_Spark解析JSON字符串并插入到MySQL数据库

业务背景&#xff1a; 最近开发有一个需求&#xff0c;是这样的 我需要将一段从前端传过来的JSON字符串进行解析&#xff0c;并从中提取出所需的数据&#xff0c;然后将这些数据插入到MySQL数据库中。 json格式样例如下 { \"区域编号\": \"001\", …...

WEB渗透—PHP反序列化(四)

Web渗透—PHP反序列化 课程学习分享&#xff08;课程非本人制作&#xff0c;仅提供学习分享&#xff09; 靶场下载地址&#xff1a;GitHub - mcc0624/php_ser_Class: php反序列化靶场课程&#xff0c;基于课程制作的靶场 课程地址&#xff1a;PHP反序列化漏洞学习_哔哩…...

LVS-DR模式部署

实验准备&#xff1a; 节点服务器 192.168.116.20 #web1 192.168.116.30 #web2 1.部署NFS共享存储 2.部署Web节点服务器 将两台服务器的网关注释掉 #重启网卡 systemctl restart network 修改节点服务器的内核参数|vim /etc/sysctl.conf net.ipv4.conf.lo.arp_ign…...

Oracle的学习心得和知识总结(三十)| OLTP 应用程序的合成工作负载生成器Lauca论文翻译及学习

目录结构 注&#xff1a;提前言明 本文借鉴了以下博主、书籍或网站的内容&#xff0c;其列表如下&#xff1a; 1、参考书籍&#xff1a;《Oracle Database SQL Language Reference》 2、参考书籍&#xff1a;《PostgreSQL中文手册》 3、EDB Postgres Advanced Server User Gui…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望

文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例&#xff1a;使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例&#xff1a;使用OpenAI GPT-3进…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

使用Spring AI和MCP协议构建图片搜索服务

目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式&#xff08;本地调用&#xff09; SSE模式&#xff08;远程调用&#xff09; 4. 注册工具提…...

从面试角度回答Android中ContentProvider启动原理

Android中ContentProvider原理的面试角度解析&#xff0c;分为​​已启动​​和​​未启动​​两种场景&#xff1a; 一、ContentProvider已启动的情况 1. ​​核心流程​​ ​​触发条件​​&#xff1a;当其他组件&#xff08;如Activity、Service&#xff09;通过ContentR…...

pikachu靶场通关笔记19 SQL注入02-字符型注入(GET)

目录 一、SQL注入 二、字符型SQL注入 三、字符型注入与数字型注入 四、源码分析 五、渗透实战 1、渗透准备 2、SQL注入探测 &#xff08;1&#xff09;输入单引号 &#xff08;2&#xff09;万能注入语句 3、获取回显列orderby 4、获取数据库名database 5、获取表名…...

Java并发编程实战 Day 11:并发设计模式

【Java并发编程实战 Day 11】并发设计模式 开篇 这是"Java并发编程实战"系列的第11天&#xff0c;今天我们聚焦于并发设计模式。并发设计模式是解决多线程环境下常见问题的经典解决方案&#xff0c;它们不仅提供了优雅的设计思路&#xff0c;还能显著提升系统的性能…...

云原生安全实战:API网关Envoy的鉴权与限流详解

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关 作为微服务架构的统一入口&#xff0c;负责路由转发、安全控制、流量管理等核心功能。 2. Envoy 由Lyft开源的高性能云原生…...

计算机系统结构复习-名词解释2

1.定向&#xff1a;在某条指令产生计算结果之前&#xff0c;其他指令并不真正立即需要该计算结果&#xff0c;如果能够将该计算结果从其产生的地方直接送到其他指令中需要它的地方&#xff0c;那么就可以避免停顿。 2.多级存储层次&#xff1a;由若干个采用不同实现技术的存储…...

接口 RESTful 中的超媒体:REST 架构的灵魂驱动

在 RESTful 架构中&#xff0c;** 超媒体&#xff08;Hypermedia&#xff09;** 是一个核心概念&#xff0c;它体现了 REST 的 “表述性状态转移&#xff08;Representational State Transfer&#xff09;” 的本质&#xff0c;也是区分 “真 RESTful API” 与 “伪 RESTful AP…...

aurora与pcie的数据高速传输

设备&#xff1a;zynq7100&#xff1b; 开发环境&#xff1a;window&#xff1b; vivado版本&#xff1a;2021.1&#xff1b; 引言 之前在前面两章已经介绍了aurora读写DDR,xdma读写ddr实验。这次我们做一个大工程&#xff0c;pc通过pcie传输给fpga&#xff0c;fpga再通过aur…...