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

B - 负环

题目描述

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

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

输入格式

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

输入的第一行是一个整数 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
3 3
1 2 3
2 3 4
3 1 -8

输出 #1复制

NO
YES

说明/提示

数据规模与约定

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

  • 1≤n≤2×10^3,1≤m≤3×10^3。
  • 1≤u,v≤n,−10^4≤w≤10^4。
  • 1≤T≤10。

提示

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

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N = 1000010;
const int INF = 0x3f3f3f3f;int n, m;
int h[N], w[N], ne[N], e[N], idx;
/*
用邻接表存储图的信息:
h[N]存储所有的表头
e[N]存储所有的边,表示边的终点
w[N]表示边的权重
ne[N]存储每个节点下一个值为多少
idx表示坐标
*/
int dist[N], cnt[N];
//dist[N]表示到某点的最短距离
//cnt[N]表示到某点的组成最短距离所用到的边数bool st[N];
//用于标记当前的点是否在队列中//加入边
void add(int a, int b, int c)
{e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx++;
}bool spfa()
{//初始化memset(dist, INF, sizeof dist);memset(st, false, sizeof st);memset(cnt, 0, sizeof cnt);//根据题目所得出的操作:从顶点1出发所能到达的负环queue<int> q;dist[1] = 0;q.push(1);st[1] = true;//直到队内没有元素为止while (q.size()){int temp = q.front(); //取出队首元素q.pop();st[temp] = false;for (int i = h[temp]; i != -1; i = ne[i]){int j = e[i];                  //当前边的终点if (dist[j] > dist[temp] + w[i]) // 如果通过当前节点可以松弛到终点j{dist[j] = dist[temp] + w[i];cnt[j] = cnt[temp] + 1;if (cnt[j] >= n) return true; //若边数为n,则证明有n+1个点,这就是一个负环if (!st[j]){q.push(j);            // 将更新的节点加入队列st[j] = true;}}}}return false;
}int main()
{int t;cin >> t;while (t--){idx = 0;cin >> n >> m;memset(h, -1, sizeof h);for (int i = 0; i < m; i++){int num1, num2, num3;cin >> num1 >> num2 >> num3;if (num3 >= 0){add(num1, num2, num3);add(num2, num1, num3);}else add(num1, num2, num3);}if (spfa()) cout << "YES" << endl;else cout << "NO" << endl;}
}

相关文章:

B - 负环

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

居中一个元素(水平+垂直居中)

我们的示例代码全在此基础上修改&#xff1a; ...... <style>* {margin: 0;padding: 0;}.par {width: 600px;height: 400px;background-color: antiquewhite;display: flex;justify-content: center;align-items: center;}.chi1 {width: 60px;height: 40px;backgrou…...

React笔记(二)JSX

一、JSX JSX是javascript XML的简写&#xff0c;实际上是javascript的扩展&#xff0c;既有javascript的语法结构&#xff0c;又有XML的结构 1、JSX的规则要求 jsx必须要有一个根节点 如果不想产生无用的根标签&#xff0c;但是还要遵守JSX的语法的要求&#xff0c;可以使用…...

[多标签分类]MultiLabelBinarizer: 从one-hot 到multi-hot

]MultiLabelBinarizer: 从one-hot 到multi-hot 背景知识One hot encoderLabelEncoderMultiLabelBinarizer总结 背景知识 多类别分类: label space至少有3个label, 且默认每个sample有一个label, 与之相对应的是二元分类Binary classification, 多标签分类: 每个sample有1至多…...

【校招VIP】前端算法考察之排序

考点介绍&#xff1a; 不同的场景中&#xff0c;不同的排序算法执行效率不同。 稳定&#xff1a;冒泡、插入、归并 不稳定&#xff1a;选择、快速、堆排序、希尔排序 『前端算法考察之排序』相关题目及解析内容可点击文章末尾链接查看&#xff01; 一、考点题目 1、使用js实…...

集创北方ICN6211 是一款MIPIDSI转RGB视频桥接IC

ICN6211 1.描述&#xff1a; ICN6211是一个桥接芯片&#xff0c;它接收MIPIDSI输入并发送RGB输出。MIPIDSI最多支持4个车道&#xff0c; 每个车道的最大运行频率为1Gbps&#xff1b;总最大输入带宽为4Gbps&#xff1b;并且还支持MIPI定义的ULPS&#xff08;超 低功耗状态&a…...

SMT制造中的产品质量检验和管理

SMT制造中的质量检验和产品物料管理都是实现高质量、低成本、高效益的重要方法。在SMT加工的过程中&#xff0c;产品质量的检验和质量把控都是重中之重&#xff0c;可以有效的降低产品不良率及返修等造成制造成本升高的风险问题&#xff0c;今天就来跟大家讨论一下SMT制造中我们…...

对接webservice接口时报错:发送方和接收方 Action 不匹配

趁着早上有时间&#xff0c;赶紧记录一下&#xff0c;哈哈。 错误提示如下&#xff1a; 1、英文版&#xff1a; <s:Envelope xmlns:s“http://schemas.xmlsoap.org/soap/envelope/”><s:Body><s:Fault>a:ActionNotSupportedThe message with Action ‘’ ca…...

python实现/直播服务器/聊天服务器/的多种解决方案

python有哪些技术栈 实现直播服务器 在Python中&#xff0c;您可以使用以下技术栈来实现直播服务器&#xff1a; Flask&#xff1a;Flask是一个轻量级的Web框架&#xff0c;可用于构建直播服务器的后端。您可以使用Flask编写API端点来处理直播流的控制和管理。 Django&#xf…...

PbootCMS 3.0.4 SQL注入

1.漏洞复现 PbootCMS 3.0.4&#xff0c;下载仓库 星梦/PbootCMS - Gitee.com 复现 漏洞页面&#xff1a;http://127.0.0.1/?search 或 http://127.0.0.1/?keyword POST请求&#xff1a;1select 1 2.正向分析 从可见功能点正向分析 index.php ... // 引用内核启动文件…...

SpringBoot异步方法支持注解@Async应用

SpringBoot异步方法支持注解Async应用 1.为什么需要异步方法&#xff1f; 合理使用异步方法可以有效的提高执行效率 同步执行(同在一个线程中): 异步执行(开启额外线程来执行): 2.SpringBoot中的异步方法支持 在SpringBoot中并不需要我们自己去创建维护线程或者线程池来…...

UI/UX设计与前端开发:从零到一打造完美用户体验

引言 在当今的软件开发领域&#xff0c;UI/UX设计和前端开发是两个密不可分的环节。UI/UX设计师负责创造出直观、美观、用户友好的界面&#xff0c;而前端开发者则将这些设计转化为实际的、可交互的网页或应用。本文将深入探讨这两个领域的交集&#xff0c;并通过代码示例来展…...

Hadoop Hdfs基本命令

0目录 1.hadoop安装问题处理 2.hdfs基本命令 3.上传/下载文件和文件夹 1.hadoop安装问题处理 如果安装有进程无法启动&#xff0c;如下图 重新检查6个配置文件 Core-site.xml \ hdfs-site.xml \ hadoop-env.sh \ yarn-site.xml \ workers \ yarn-site.xml 来到hadoop313目录…...

Spring Boot 整合MyBatis(超详细)

&#x1f600;前言 本篇博文关于Spring Boot 整合MyBatis&#xff0c;希望你能够喜欢 &#x1f3e0;个人主页&#xff1a;晨犀主页 &#x1f9d1;个人简介&#xff1a;大家好&#xff0c;我是晨犀&#xff0c;希望我的文章可以帮助到大家&#xff0c;您的满意是我的动力&#x…...

【管理运筹学】第 6 章 | 运输问题(4,表上作业法 |闭回路调整法以及特殊情况 | 产销不平衡的运输问题)

文章目录 引言二、表上作业法2.3 改进的方法 —— 闭回路调整法2.4 表上作业法中的特殊情况&#xff08;一&#xff09;无穷多最优解&#xff08;二&#xff09;退化 三、产销不平衡的运输问题3.1 产量大于销量3.2 销量大于产量 写在最后 引言 接下来我们学习表上作业法的最后…...

Greenplum实用技巧

一、通过gp_segment_id查看数据倾斜 gp_segment_id是表中的隐藏列&#xff0c;用来标记该行属于哪个segment节点。因此可以基于该隐藏列进行分组查询&#xff0c;获取每个segment的记录数&#xff0c;从而判断表数据的分布是否均匀或有倾斜。 qb#select gp_segment_id, count…...

以物联网为核心的智慧工地云平台:聚集智能技术,实现建筑工地智慧管理

智慧工地云平台源码&#xff0c;智慧工地项目监管平台源码&#xff0c;智慧工地可视化数据大屏源码 智慧工地云平台是将云计算、大数据、物联网、移动技术和智能设备等信息化技术手段&#xff0c;聚集在建筑工地施工管理现场&#xff0c;围绕人员、机械、物料、环境等关键要素&…...

Java项目-苍穹外卖-Day05-Redis技术应用

1.店铺营业状态设置 需求分析和设计 左上角要求是有回显的 所以至少两个接口 1.查询营业状态接口&#xff08;分为了管理端和用户端&#xff09; 2.修改营业状态接口 因为管理端和用户端路径不同&#xff0c;所以现在是至少三个接口的 可以发现如果存到表里除了id只有一个…...

linux安装jmeter

linux安装jmeter 部署java1.8 下载jmeter安装包&#xff1a;官网、网盘5.6.2版本 # 解压 rootiZbp1at7nu2rpq4xn4zaf1Z:/opt/jmeter# sudo tar -xzf apache-jmeter-5.6.2.tgz # 加入环境变量 rootiZbp1at7nu2rpq4xn4zaf1Z:/opt/jmeter/apache-jmeter-5.6.2# export JMETER/op…...

【笔记】泛型以及如何绕过泛型定义

泛型定义以及其带来的好处 泛型使类型&#xff08;类和接口&#xff09;能够在定义类、接口和方法时成为参数。与方法声明中使用的更熟悉的形式参数非常相似&#xff0c;类型参数为您提供了一种通过不同输入重复使用相同代码的方法。区别在于形式参数的输入是值&#xff0c;而…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

前端倒计时误差!

提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

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

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

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

Java毕业设计:WML信息查询与后端信息发布系统开发

JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发&#xff0c;实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构&#xff0c;服务器端使用Java Servlet处理请求&#xff0c;数据库采用MySQL存储信息&#xff0…...

MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用

文章目录 一、背景知识&#xff1a;什么是 B-Tree 和 BTree&#xff1f; B-Tree&#xff08;平衡多路查找树&#xff09; BTree&#xff08;B-Tree 的变种&#xff09; 二、结构对比&#xff1a;一张图看懂 三、为什么 MySQL InnoDB 选择 BTree&#xff1f; 1. 范围查询更快 2…...