当前位置: 首页 > 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;而…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器

一.自适应梯度算法Adagrad概述 Adagrad&#xff08;Adaptive Gradient Algorithm&#xff09;是一种自适应学习率的优化算法&#xff0c;由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率&#xff0c;适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

selenium学习实战【Python爬虫】

selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...

USB Over IP专用硬件的5个特点

USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中&#xff0c;从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备&#xff08;如专用硬件设备&#xff09;&#xff0c;从而消除了直接物理连接的需要。USB over IP的…...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...

PAN/FPN

import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...