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

拓扑排序求最长路

P1807 最长路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目要求我们求出第1号到第n号节点之间最长的距离。

我们想到使用拓扑排序来求最长路。

正常来讲,我们应该把1号节点入队列,再出队列,把一号节点能到达的所有的点的入度减一,并且将这些点求到达一号节点的最大距离。如果一个节点的入度为0,那说明所有与他直接来链接的点都跑了一边,最后最大的也就跑出来了。即使任意两个点有多条链接路径也不碍事,为什么呢?举个例子,一号和二号点有三条路径分别为1,2,3,我们放进队列里后,会先后跑这三段长度最后取得最优。但是这道题目有个小坑点,那就是这种情况

这种情况下我们初始时期是只存入了一号节点所置。

由于3号节点还有一条入度,而2号节点我们没有初始化放入,即使他的入度为0也不能进入队列,所以3号节点无法到达,但实际1号节点可以到达3号节点,解决方法就是首先把非1号的所有的入度为0的节点先入队列,然后排除干扰,最后就可以按照原步骤进行了。

附上代码


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.math.MathContext;
import java.security.PublicKey;
import java.sql.SQLIntegrityConstraintViolationException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.TreeMap;
import java.util.TreeSet;
public class Main {	public static void main(String[] args) throws NumberFormatException, IOException  {
Scanner sc=new Scanner(System.in);
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw1=new PrintWriter(System.out);
String[] aStrings=br.readLine().split(" ");
aa=Integer.parseInt(aStrings[0]);
bb=Integer.parseInt(aStrings[1]);
al1=new ArrayList[aa+1];
int a;
rudu=new int[aa+1];
for(a=1;a<=aa;a++) {al1[a]=new ArrayList<>();
}
for(a=1;a<=bb;a++) {String[] bStrings=br.readLine().split(" ");int b=Integer.parseInt(bStrings[0]);int c=Integer.parseInt(bStrings[1]);int d=Integer.parseInt(bStrings[2]);al1[b].add(new edge(c, d));//存储边rudu[c]++;//入度加一
}for(a=2;a<=aa;a++) {if(rudu[a]==0) {//为了解决上述问题我们从2号节点开始,来求得所有入读为0的点的序号ll1.add(a);}
}
dis=new int[aa+1];
Arrays.fill(dis, Integer.MIN_VALUE);
dis[1]=0;//初始点到初始点的距离肯定为0
ll1.add(1);//在这里最后加入初始点
while(ll1.size()!=0) {//取出入读为0的点int a1=ll1.remove();for(edge b1:al1[a1]) {dis[b1.to]=Math.max(dis[b1.to], dis[a1]+b1.length);rudu[b1.to]--;//进行值得更改if(rudu[b1.to]==0) {//入度为0那么就加入队列ll1.add(b1.to);}}}
if(dis[aa]==Integer.MIN_VALUE) {System.out.println("-1");
}
else {System.out.println(dis[aa]);
}}public static int aa;//点的总数public static int bb;//边的总数public static ArrayList<edge>[] al1;//存储边的集合public static int[] rudu;//记录每一个点的入度public static LinkedList<Integer> ll1=new LinkedList<>();//记录每一个入度为0的点public static int[] dis;//记录每个点距离初始点的距离。}
class edge{int to;int length;public edge(int to, int length) {super();this.to = to;this.length = length;}}

相关文章:

拓扑排序求最长路

P1807 最长路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题目要求我们求出第1号到第n号节点之间最长的距离。 我们想到使用拓扑排序来求最长路。 正常来讲&#xff0c;我们应该把1号节点入队列&#xff0c;再出队列&#xff0c;把一号节点能到达的所有的点的入度减一&a…...

sqli-lab靶场通关

文章目录 less-1less-2less-3less-4less-5less-6less-7less-8less-9less-10 less-1 1、提示输入参数id&#xff0c;且值为数字&#xff1b; 2、判断是否存在注入点 id1报错&#xff0c;说明存在 SQL注入漏洞。 3、判断字符型还是数字型 id1 and 11 --id1 and 12 --id1&quo…...

使用 Apache Camel 和 Quarkus 的微服务(五)

【squids.cn】 全网zui低价RDS&#xff0c;免费的迁移工具DBMotion、数据库备份工具DBTwin、SQL开发工具等 在本系列的第三部分中&#xff0c;我们了解了如何在 Minikube 中部署基于 Quarkus/Camel 的微服务&#xff0c;这是最常用的 Kubernetes 本地实现之一。虽然这样的本地…...

Ubuntu磁盘满了,导致黑屏

前言 &#xff08;1&#xff09;最近要玩Milk-V Duo&#xff0c;配置环境过程中&#xff0c;发现磁盘小了。于是退出虚拟机&#xff0c;扩大Ubuntu大小&#xff0c;重新开机&#xff0c;发现无法进入Ubuntu界面。 &#xff08;2&#xff09;查了很久&#xff0c;后面发现是磁盘…...

安装sklearn包错误解决以及 scikit-learn简介

安装sklearn包错误解决以及 scikit-learn简介 利用 pip install sklearn时出现错误 pip install sklearn Looking in indexes: https://mirrors.aliyun.com/pypi/simple/ Collecting sklearnUsing cached https://mirrors.aliyun.com/pypi/packages/b9/0e/b2a4cfaa9e12b9ca4…...

CSS点击切换或隐藏盒子的卷起、展开效果

<template><div class"main"><el-button click"onCllick">切换</el-button><transition name"slideDown"><div class"info" v-if"isShow">1111</div></transition></di…...

关于信息安全软考的一些记录1

1、网络信息安全的基本属性 机密性&#xff1a;网络信息不泄露给非授权的用户完整性&#xff1a;未经授权必能改的特性可用性&#xff1a;可以及时获取网络信息和服务的特性可控性&#xff1a;责任主体对网络信息系统具有管理、支配的能力【可管理、可支配】扛抵赖性&#xff…...

如何选择UMLChina服务

服务口号&#xff1a;聚焦最后一公里 斐力庇第斯从马拉松跑回雅典报信&#xff0c;虽然已是满身血迹、精疲力尽&#xff0c;但他知道&#xff1a;没有出现在雅典人民面前&#xff0c;前面的路程都是白费。 学到的知识如果不能最终【用】于您自己的项目之中&#xff0c;也同样是…...

关于信息安全软考的记录3

1、网络安全体系的特征 网络安全体系&#xff1a;网络安全保障系统的最高层概念抽象 特征内容整体性网络安全单元按照一定的规则&#xff0c;相互依赖、相互作用而形成人机物一体化的网络安全保护方式协同性通过各种安全机制的相互协作&#xff0c;构建系统性的网络安全保护方…...

API攻防-接口安全SOAPOpenAPIRESTful分类特征导入项目联动检测

文章目录 概述什么是接口&#xff1f; 1、API分类特征SOAP - WSDLWeb services 三种基本元素&#xff1a; OpenApi - Swagger UISpringboot Actuator 2、API检测流程Method&#xff1a;请求方法URL&#xff1a;唯一资源定位符Params&#xff1a;请求参数Authorization&#xff…...

【Docker 内核详解】namespace 资源隔离(二):UTS namespace IPC namespace

namespace 资源隔离&#xff08;二&#xff09;&#xff1a;UTS namespace & IPC namespace 1.UTS namespace UTS&#xff08;UNIX Time-sharing System&#xff09;&#xff0c;UTS namespace 提供了 主机名 和 域名 的隔离&#xff0c;这样每个 Docker 容器就可以拥有独…...

EOF() | BOF()相关题目解析

题目 设当前数据库有10条记录(记录未进行任何索引)&#xff0c;在下列3种情况下&#xff0c;当前记录号为1时&#xff1a;EOF()为真时&#xff1b;BOF()为真时&#xff0c;命令RECN()的结果分别是______。 A&#xff0e;1,11,1B&#xff0e;1,10,1C&#xff0e;1,11,0D&#xf…...

spring 注入 当有两个参数的时候 接上面

新加一个int 型的 age 记得写getset方法和构造方法 &#xff08;&#xff08;&#xff08;&#xff08;&#xff08;&#xff08;&#xff08; 构造方法的作用——无论是有参构造还是无参构造&#xff0c;他的作用都是为了方便为对象的属性初始化值 构造方法是一种特殊的方…...

博客文档续更

十、 博客前台模块-异常处理 目前我们的项目在认证出错或者权限不足的时候响应回来的Json&#xff0c;默认是使用Security官方提供的响应的格式&#xff0c;但是这种响应的格式肯定是不符合我们项目的接口规范的。所以需要自定义异常处理 我们需要去实现AuthenticationEntryP…...

OCR让点读笔如虎添翼

点读笔是一种智能学习工具&#xff0c;它可以通过识别文字来提供相应的语音或图像反馈。在实现文字识别功能时&#xff0c;点读笔通常会借助OCR&#xff08;Optical Character Recognition&#xff0c;光学字符识别&#xff09;技术。下面将详细介绍点读笔如何利用OCR技术实现文…...

棱镜七彩参编!开源领域4项团体标准正式发布

近日&#xff0c;中电标2023年第27号团体标准公告正式发布&#xff0c;《T/CESA 1270.2-2023 信息技术 开源治理 第 2 部分&#xff1a;企业治理评估模型》、《T/CESA 1270.3-2023 信息技术 开源治理 第 3 部分&#xff1a;社区治理框架》、《T/CESA 1270.5-2023 信息技术 开源…...

轻量级Composition

MEF&#xff0c;全称Managed Extensibility Framework&#xff08;托管可扩展框架&#xff09;。MEF是专门致力于解决扩展性问题的框架。MEF 位于 ComponentModel.Composition 程序集中&#xff0c;添加 System.ComponentModel.Composition 和 System.ComponentModel.Compositi…...

Vxlan网络和flannel记录

Vxlan 大二层网络&#xff0c;在三层网络中构建逻辑的2层网络 数据包经过vxlan隧道 用vni标识不同的vxlan网络&#xff08;类似于vlan的vid&#xff09; 通过vtep来封装和解封装&#xff0c;通过UDP传输 Flannel 分配子网和IP地址&#xff1a;Flannel为每个容器或虚拟机分配唯一…...

【已解决】微信小程序-苹果手机日期解析异常

在开发微信小程序时&#xff0c;使用了 uView 的 CountDown倒计时 组件和 uni.$u.timeFrom Api&#xff0c;后台传递了一个时间字符串&#xff0c;前台计算时间戳的差值&#xff0c;来显示还有多久开始&#xff0c;这个功能在模拟器和我自己手机&#xff08;iphon13&#xff09…...

Avalonia如何更改全局背景色

1.项目下载地址&#xff1a;https://gitee.com/confusedkitten/avalonia-demo 2.UI库Semi.Avalonia&#xff0c;项目地址 https://github.com/irihitech/Semi.Avalonia 3.ColorView&#xff0c;使用Semi.Avalonia.ColorPicker&#xff0c;Nuget获取就行 4.样式预览 以下是…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

Android Wi-Fi 连接失败日志分析

1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分&#xff1a; 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析&#xff1a; CTR…...

【kafka】Golang实现分布式Masscan任务调度系统

要求&#xff1a; 输出两个程序&#xff0c;一个命令行程序&#xff08;命令行参数用flag&#xff09;和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽&#xff0c;然后将消息推送到kafka里面。 服务端程序&#xff1a; 从kafka消费者接收…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

Springboot社区养老保险系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;社区养老保险系统小程序被用户普遍使用&#xff0c;为方…...

Java 二维码

Java 二维码 **技术&#xff1a;**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...