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

P1113 杂务-拓扑排序

news 来源：原创 2025/8/10 19:59:40
拓扑排序

P1113 杂务

题目来源-洛谷
在这里插入图片描述
题意

求出完成所有任务的最短时间

思路

  1. 要求完成所有任务的最短时间，即每个任务尽可能最短，所以再求完成所有任务中的最大值（需要最长时间的任务都完成了才叫全部完成）

  2. 问题化解：想办法求每个人的完成的最短时间（子任务中的最长时间+完成当前任务的时间）-动态规划的思想，用数组保存子任务的完成时间，然后 time[x] = max(所有子任务的完成时间-time[i]) +当前任务时间

  3. 如何求所有子任务的时间？

    dfs遍历求其子任务时间 time[x] = max(dfs(子任务)-time[i]) +当前任务时间

    最后，最终结果ans = max(每个节点的最短时间) 即 ans = max(ans,dfs(i)) ,i = [1,n]

数据约束

注意数组长度即可

参考代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+5;
int dfs(int k);
int m,n;//n个点
vector<int> p[MAXN];//邻接表存图 
int t[MAXN],f[MAXN] ;//存每个任务的时间 和完成该任务所需的最短时间 
int ans ;//存结果 
int main(){ cin>>n;int x,l,rw;//分别表示节点，完成的时间 ,必须完成的任务 for(int i=0;i<n;i++){cin>>x;cin>>t[x];while(cin>>rw){if(rw){//非0都可以说明有必须准备的任务p[x].push_back(rw);//反向存图 }else break;}} //	查看储存的数据是否正确 
//	for(int i=1;i<=n;i++){
//		for(int j=0;j<p[i].size();j++){
//			cout<<p[i][j]<<":"<<t[p[i][j]]<<" 、"; 
//		} 
//		cout<<endl;
//	}for(int i=1;i<=n;i++){ans = max(ans,dfs(i)) ;//找所有任务的最大值 } cout<<ans;return 0;
}
int dfs(int k){if(f[k]) return f[k];//有值说明访问过 for(int i=0;i<p[k].size();i++){//if(!f[p[k][i]]) 因为做当前任务都需要求出子任务最大时间，所以判断是否访问没有意思 //当前节点的完成时间是其所有子任务的最大时间+自身完成的时间f[k] = max(f[k],dfs(p[k][i]));}f[k] += t[k];//所有子任务遍历完后再来算当前值 return f[k] ;
}

相关文章：

P1113 杂务-拓扑排序

拓扑排序 P1113 杂务 题目来源-洛谷 题意 求出完成所有任务的最短时间 思路 要求完成所有任务的最短时间&#xff0c;即每个任务尽可能最短&#xff0c;所以再求完成所有任务中的最大值&#xff08;需要最长时间的任务都完成了才叫全部完成&#xff09; 问题化解&#xf…...

编程日记 2025/8/10 19:59:40

Flink介绍——实时计算核心论文之Kafka论文总结

引入 大数据系统中的数据来源 在开始深入探讨Kafka之前&#xff0c;我们得先搞清楚一个问题&#xff1a;大数据系统中的数据究竟是从哪里来的呢&#xff1f;其实&#xff0c;这些数据大部分都是由各种应用系统或者业务系统产生的“日志”。 比如&#xff0c;互联网公司的广告…...

编程日记 2025/8/9 3:58:01

模拟投资大师思维：AI对冲基金开源项目详解

这里写目录标题 引言项目概述核心功能详解多样化的AI投资智能体灵活的运行模式透明的决策过程 安装和使用教程环境要求安装步骤基本使用方法运行对冲基金模式运行回测模式 应用场景和实际价值教育和研究价值潜在的商业应用与现有解决方案的对比局限性与发展方向 结论 引言 随着…...

编程日记 2025/7/31 2:35:41

DAY4:数据库对象与高级查询深度解析：从视图到多表关联实战

一、数据库对象精要指南 1.1 视图&#xff08;View&#xff09;的进阶应用 视图是存储在数据库中的虚拟表&#xff0c;本质是预编译的SQL查询语句。通过视图可以简化复杂查询、实现数据安全隔离、保持业务逻辑一致性。 创建语法示例&#xff1a; CREATE VIEW sales_summary…...

编程日记 2025/8/7 10:35:57

【Matlab】中国东海阴影立体感地图

【Matlab】中国东海阴影立体感地图 【Matlab】中国东海阴影立体感地图 【Matlab】中国东海阴影图立体感画法 以前分享过一次&#xff0c;链接如下&#xff1a; 中国海域地形图 但是以前还是有些小问题&#xff0c;这次修改了。 另外&#xff0c;增加了新的画法&#xff1a; 另…...

编程日记 2025/8/8 20:27:02

python文件类操作：json/ini配置文件、logging日志统计、excel表格数据读写、os操作库

文章目录 一、with open文件操作二、csv表格数据读写三、Excel表格数据读写四、json配置文件读写五、ini配置文件读写六、logging日志统计七、os操作库&#xff08;文件拼接、创建、判断等&#xff09; 打开文件使用不同参数有着不同的含义&#xff0c;比如只读、只写、二进制读…...

编程日记 2025/8/10 12:27:11

VSCode安装与环境配置（Mac环境）

20250419 - 概述 大概是非常久之前了&#xff0c;装了VSCode&#xff0c;估计都得21的时候了&#xff0c;电脑上也没更新过。当时安装也直接装上就完事了。这次把版本更新一下&#xff0c;同时记录一下这个安装过程。 安装 mac下安装非常简单&#xff0c;直接从官网下载&am…...

编程日记 2025/8/9 5:50:01

【信息系统项目管理师】高分论文：论信息系统项目的采购管理（“营业工单系统”项目）

更多内容请见： 备考信息系统项目管理师-专栏介绍和目录 文章目录 论文1、规划采购管理2、实施采购3、控制采购论文 2018年1月，我参加了 XX运营商集团公司某省分公司的“营业工单系统”的信息化建设项目，我有幸担任项目经理。该项目投资1000万元人民币，建设工期为12个月。该…...

编程日记 2025/8/10 19:57:27

XCVU13P-2FHGA2104I Xilinx Virtex UltraScale+ FPGA

XCVU13P-2FHGA2104I 是 Xilinx&#xff08;现为 AMD&#xff09;Virtex UltraScale™ FPGA 系列中的高端 Premium 器件&#xff0c;基于 16nm FinFET 工艺并采用 3D IC 堆叠硅互连&#xff08;SSI&#xff09;技术&#xff0c;提供业内顶级的计算密度和带宽​。该芯片集成约 3,…...

编程日记 2025/8/5 12:07:34

@Validated与@Valid的正确使用姿势

验证代码 Validated RestController public class A {PostMappingpublic void test(Min(value 1) Integer count) {} // 校验规则生效 }RestController public class A {PostMappingpublic void test(Validated Min(value 1) Integer count) {} // 校验规则不生效 }RestCont…...

编程日记 2025/8/8 9:51:51

Ubuntu20.04下Docker方案实现多平台SDK编译

0 前言 熟悉嵌入式平台Linux SDK编译流程的小伙伴都知道，假如平台a要求必须在Ubuntu18.04下编译，平台b要求要Ubuntu22.04的环境，那我只有Ubuntu20.04，或者说我的电脑硬件配置最高只能支持Ubuntu20.04怎么办？强行在Ubuntu20.04下编译，编又编不过，换到旧版本我又不愿意，…...

编程日记 2025/8/3 14:01:27

树莓派超全系列教程文档--(34)树莓派配置GPIO

配置GPIO GPIO控制gpio 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 GPIO控制 gpio 通过 gpio 指令&#xff0c;可以在启动时将 GPIO 引脚设置为特定模式和值&#xff0c;而以前需要自定义 dt-blob.bin 文件。每一行都对一组引脚应用相同的设…...

编程日记 2025/7/31 5:13:10

C语言 数组(下)

目录 1.二维数组的创建 2.二位数组的初始化 3.二维数组的使用 4.二维数组在内存中的储存 1.二维数组的创建 1.1二维数组的概念 前面学习的数组被称为一维数组&#xff0c;数组的元素都是内置类型的&#xff0c;如果我们把一维数组做为数组的元 素&#xff0c;这时候就是…...

编程日记 2025/8/6 5:07:22

opencv图像旋转(单点旋转的原理）

首先我们以最简单的一个点的旋转为例子&#xff0c;且以最简单的情况举例&#xff0c;令旋转中心为坐标系中心O&#xff08;0&#xff0c;0&#xff09;&#xff0c;假设有一点P_{0}(x_{0},y_{0})&#xff0c;P_{0}离旋转中心O的距离为r&#xff0c;OP_{0}与坐标轴x轴的夹角为\…...

编程日记 2025/8/8 12:27:37

针对MCP认证考试中的常见技术难题进行实战分析与解决方案分享

一、身份与权限管理类难题 场景1&#xff1a;Active Directory组策略&#xff08;GPO&#xff09;不生效 问题现象&#xff1a;客户端计算机未应用新建的组策略。排查步骤&#xff1a; 检查GPO链接顺序&#xff1a;使用gpresult /r查看策略优先级&#xff0c;确保目标OU的GPO…...

编程日记 2025/8/8 18:12:36

systemctl管理指令

今天我们来继续学习服务管理指令,接下来才是重头戏-systemctl,那么话不多说,直接开始吧. systemctl管理指令 1.基本语法: systemctl [start | stop | restart | status]服务 注&#xff1a;systemctl指令管理的服务在/usr/lib/ systemd/system查看 2.systemctl设置服务的自…...

编程日记 2025/8/9 23:38:57

DataWhale AI春训营 问题汇总

1.没用下载训练集导致出错&#xff0c;爆错如下。 这个时候需要去比赛官网下载对应的初赛训练集 unzip -d /mnt/workspace/sais_third_new_energy_baseline/data /mnt/workspace/sais_third_new_energy_baseline/初赛训练集.zip 在命令行执行这个命令解压 2.没定义测试集 te…...

编程日记 2025/8/8 20:22:00

当算力遇上马拉松：一场科技与肉身的极限碰撞

目录 一、从"肉身苦修"到"科技修仙" 二、马拉松的"新大陆战争" 三、肉身会被算法"优化"吗？ 马拉松的下一站是"人机共生"时代 当AI能预测你的马拉松成绩，算法能规划最佳补给方案，智能装备让训练效率翻倍——你还会用传…...

编程日记 2025/8/6 23:57:18

n8n 中文系列教程_02. 自动化平台深度解析：核心优势与场景适配指南

在低代码与AI技术深度融合的今天&#xff0c;n8n作为开源自动化平台正成为开发者提效的新利器。本文深度剖析其四大核心技术优势——极简部署、服务集成、AI工作流与混合开发模式&#xff0c;并基于真实场景测试数据&#xff0c;厘清其在C端高并发、多媒体处理等场景的边界。 一…...

编程日记 2025/8/10 19:59:20

Macvlan 网络类型详解：特点、优势与局限性

一、Macvlan 网络类型的基本概念 1. 什么是 Macvlan Macvlan 是 Linux 内核提供的一种网络虚拟化技术&#xff0c;允许在单个物理接口&#xff08;例如 enp0s3&#xff09;上创建多个虚拟网络接口。每个虚拟接口拥有独立的 MAC 地址&#xff0c;表现得像物理网络中的独立设备…...

编程日记 2025/8/6 19:33:42

tigase源码学习杂记-AbstractMessageReceiver

前言 废话&#xff0c;最近把工作中用的基于XMPP协议的经典开源框架又读了一遍&#xff0c;整理一下其优秀的源码学习记录。 概述 AbstractMessageReceiver是tigase核心组件MessageRouter、SessionManager的抽象父类&#xff0c;是tigase消息接收器的抽象。AbstractMessageR…...

编程日记 2025/8/8 23:16:15

C#.net core部署IIS

Windows IIS 部署 .NET 应用详细指南 本文档提供了在 Windows Server 上使用 IIS 部署 .NET 应用&#xff08;包括 .NET Core 和传统 WebForms&#xff09;的完整步骤和最佳实践。 目录 概述环境准备.NET Core 应用部署 应用准备发布应用在 IIS 中配置应用池配置高级配置 .N…...

编程日记 2025/8/2 23:59:33

sql学习

Name 列中选取唯一不同的值 插入 更新 删除 筛选固定的行数 模糊查询 包含 范围 name的别名是n 两个表交集 左边包含全部 右边包含全部 重复的展示一条 重复的都会展示 创建一个新表&#xff0c;把字段复制近期 创建数据库 约束 创建索引 删除 函数 聚合函数...

编程日记 2025/8/8 9:37:06

OSPF实验

实验要求&#xff1a; 1.R5为ISP&#xff0c;其上只能配置IP地址&#xff1b;R4作为企业边界路由器&#xff0c; 出口公网地址需要通过PPP协议获取&#xff0c;并进行chap认证 &#xff08;上面这个不会做&#xff09; 2.整个OSPF环境IP基于172.16.0.0/16划分&#xff1b; 3.所…...

编程日记 2025/7/31 5:12:48

洛谷题目：P8624 [蓝桥杯 2015 省 AB] 垒骰子 题解 （本题简）

题目传送门： P8624 [蓝桥杯 2015 省 AB] 垒骰子 - 洛谷 (luogu.com.cn) 前言： 这道题要求我们计算将 个骰子垒成柱体且满足某些面不能紧贴的不同垒骰字方式的数量，并且结果需要对 取模。下面小亦来带大家逐步分析解题思路： #基本概念理解： 1、骰子特性： 一直骰子的…...

编程日记 2025/8/10 1:23:06

简单线段树的讲解（一点点的心得体会）

目录 一、初识线段树 图例&#xff1a; ​编辑 数组存储&#xff1a; 指针存储&#xff1a; 理由&#xff1a; build函数建树 二、线段树的区间修改维护 区间修改维护&#xff1a; 区间修改的操作&#xff1a; 递归更新过程&#xff1a; 区间修改update&#xff1a…...

编程日记 2025/8/6 20:34:37

在 Node.js 中使用原生 `http` 模块，获取请求的各个部分：**请求行、请求头、请求体、请求路径、查询字符串** 等内容

在 Node.js 中使用原生 http 模块&#xff0c;可以通过 req 对象来获取请求的各个部分&#xff1a;请求行、请求头、请求体、请求路径、查询字符串 等内容。 ✅ 一、基础结构 const http require(http); const url require(url);const server http.createServer((req, res)…...

编程日记 2025/8/10 19:32:07

深度学习--mnist数据集实现卷积神经网络的手写数字识别

文章目录 一、卷积神经网络CNN1、什么是CNN2、核心3、构造 二、案例1、下载数据集&#xff08;训练、测试集&#xff09;并展示画布2、打包数据图片3、判断系统使用的是CPU还是GPU4、定义CNN神经网络5、训练和测试模型 一、卷积神经网络CNN 1、什么是CNN 卷积神经网络是一种深…...

编程日记 2025/8/9 17:42:02

python基础知识点（1）

python语句 一行写一条语句 一行内写多行语句&#xff0c;使用分号分隔建议每行写一句&#xff0c;且结束时不写分号写在[ ]、{ }内的跨行语句&#xff0c;被视为一行语句\ 是续行符,实现分行书写功能 反斜杠表示下一行和本行是同一行 代码块与缩进 代码块复合语句&#xf…...

编程日记 2025/8/10 4:50:38

详解反射型 XSS 的后续利用方式：从基础窃取到高级组合拳攻击链

在网络安全领域&#xff0c;反射型跨站脚本攻击&#xff08;Reflected Cross-Site Scripting&#xff0c;简称反射型 XSS&#xff09;因其短暂的生命周期和临时性&#xff0c;常被视为“低危”漏洞&#xff0c;威胁性不如存储型或 DOM 型 XSS。然而&#xff0c;这种看法低估了它…...

编程日记 2025/8/9 8:18:54

【问题笔记】解决python虚拟环境运行脚本无法激活问题

【问题笔记】解决python虚拟环境运行脚本无法激活问题 错误提示问题所在解决方法**方法 1&#xff1a;临时更改执行策略****方法 2&#xff1a;永久更改执行策略** **完整流程示例** 错误提示 PS F:\PythonProject\0419graphrag-local-ollama-main> venv1\Scripts\activate…...

编程日记 2025/8/8 15:36:28

CF148D Bag of mice

题目传送门 思路 状态设计 设 d p i , j dp_{i, j} dpi,j​ 表示袋中有 i i i 个白鼠和 j j j 个黑鼠时&#xff0c; A A A 能赢的概率。 状态转移 现在考虑抓鼠情况&#xff1a; A A A 抓到白鼠&#xff1a;直接判 A A A 赢&#xff0c;概率是 i i j \frac{i}{i j}…...

编程日记 2025/8/4 16:22:49

精益数据分析（6/126）：深入理解精益分析的核心要点

精益数据分析&#xff08;6/126&#xff09;&#xff1a;深入理解精益分析的核心要点 在创业和数据驱动的时代浪潮中&#xff0c;我们都在不断探索如何更好地利用数据推动业务发展。我希望通过和大家分享对《精益数据分析》的学习心得&#xff0c;一起在这个充满挑战和机遇的领…...

编程日记 2025/8/5 22:27:26

package.json ^、~、＞、＞=、* 详解

package.json ^、~、>、>、* 详解 在 Vue 项目中&#xff0c;package.json 文件的依赖项&#xff08;dependencies&#xff09;和开发依赖项&#xff08;devDependencies&#xff09;中&#xff0c;版本号前可能会带有一些特殊符号&#xff0c;例如 ^、~、>、<、&g…...

编程日记 2025/8/9 8:43:28

2025年赣教云智慧作业微课PPT模板

江西的老师们注意&#xff0c;2025年赣教云智慧作业微课PPT模版和往年不一样&#xff0c;千万不要搞错了&#xff0c;图上的才是正确的2025年的赣教云智慧作业微课PPT模版&#xff0c;赣教云智慧作业官网有问题&#xff0c;无法正确下载该模板&#xff0c;需要该模板的&#xf…...

编程日记 2025/8/6 13:21:57

Java PrintStream 类深度解析

Java PrintStream 类深度解析 便捷： 1.直接输出各种数据 2.自动刷新和自动换行（println方法） 3.支持字符串转义 4.自动编码（自动根据环境选择合适的编码方式） 1. 核心定位 PrintStream 是 FilterOutputStream 的子类，提供格式化输出能力，是标准输出 System.out 的…...

编程日记 2025/8/9 1:30:15

超简单的git学习教程

本博客仅用于记录学习和使用 前提声明全部内容全部来自下面廖雪峰网站&#xff0c;如果侵权联系我删除 1.小白学习看这篇&#xff0c;快速易懂入门&#xff0c;完整内容&#xff08;半天完成学习本地和远程仓库建立&#xff09; 简介 - Git教程 - 廖雪峰的官方网站 2.博客中…...

编程日记 2025/8/6 12:39:44

Yocto项目实战教程-第5章-5.1-5.2小节-BitBake的起源与源代码讲解

&#x1f50d; B站相应的视频教程&#xff1a; &#x1f4cc; Yocto项目实战教程-第5章-5.1-5.2小节-BitBake的起源与源代码讲解 记得三连&#xff0c;标为原始粉丝。 &#x1f4da; 系列持续更新中&#xff0c;B站搜索 “嵌入式 Jerry”&#xff0c;系统学 Yocto 不迷路&#…...

编程日记 2025/8/8 8:28:17

SQL注入相关知识

一、布尔盲注 1、布尔盲简介 布尔盲注是一种SQL注入攻击技术&#xff0c;用于在无法直接获取数据库查询结果的情况下&#xff0c;通过页面的响应来判断注入语句的真假&#xff0c;从而获取数据库中的敏感信息 2、布尔盲注工作原理 布尔盲注的核心在于利用SQL语句的布尔逻辑…...

编程日记 2025/8/6 16:11:43

Linux网络编程 深入解析Linux TCP：TCP实操，三次握手和四次挥手的底层分析

知识点1【TCP编程概述】 1、TCP的概述 客户端&#xff1a;主动连接服务器&#xff0c;和服务器进行通信 服务器&#xff1a;被动被客户端连接&#xff0c;启动新的线程或进程&#xff0c;服务器客户端&#xff08;并发服务器&#xff09; 这里重复TCP和UDP特点 TCP&#x…...

编程日记 2025/8/10 0:47:50

实验4基于神经网络的模式识别实验

实验原理 1. BP学习算法是通过反向学习过程使误差最小&#xff0c;其算法过程从输出节点开始&#xff0c;反向地向第一隐含层(即最接近输入层的隐含层)传播由总误差引起的权值修正。BP网络不仅含有输入节点和输出节点&#xff0c;而且含有一层或多层隐(层)节点。输入信号先向前…...

编程日记 2025/7/31 5:12:16

Rust网络编程实战：全面掌握reqwest库的高级用法

一、开篇导引 1.1 对比Python Requests解释为何reqwest是Rust生态的标杆HTTP客户端 在Python生态中&#xff0c;Requests 库以其简洁易用的API成为了HTTP客户端的首选。它使得开发者能够轻松地发送各种HTTP请求&#xff0c;处理响应&#xff0c;而无需过多关注底层细节。然而…...

编程日记 2025/8/9 7:40:06

【漫话机器学习系列】211.驻点（Stationary Points）

驻点&#xff08;Stationary Points&#xff09;&#xff1a;理解函数导数为零的关键位置 在数学分析、机器学习优化、物理建模等领域中&#xff0c;驻点&#xff08;Stationary Points&#xff09;是一个非常重要的概念。它们是函数图像中“停下来的点”&#xff0c;即导数为…...

编程日记 2025/8/6 16:21:14

图 - 最小生成树算法 - Kruskal - Prim

目录 前言 什么是最小生成树算法 Kruskal 克鲁斯卡尔 Prim 普利姆 结语 前言 在图中一共有两类算法&#xff0c;一种是最短路径&#xff0c;还有一种就是本篇要讲解的最小生成树算法了 其中&#xff0c;最短路径一共有三种&#xff0c;而最小生成树一共有两种&#xff…...

编程日记 2025/8/7 21:48:07

linux kernel irq相关函数详解

在Linux内核驱动开发中&#xff0c;处理中断涉及一系列关键函数&#xff0c;正确使用这些函数对确保驱动的稳定性和性能至关重要。以下是disable_irq、free_irq、platform_get_irq和request_irq等函数的详细解析&#xff0c;涵盖其功能、用法、注意事项及示例代码。 一、核心函…...

编程日记 2025/8/7 8:14:49

聊聊Doris的数据模型，如何用结构化设计解决实时分析难题

传统 OLAP 系统的局限 在大数据实时分析领域&#xff0c;数据模型设计直接决定了系统的查询性能、存储效率与业务适配性。Apache Doris作为新一代MPP分析型数据库&#xff0c;通过独创的多模型融合架构&#xff0c;在业内率先实现了"一份数据支持多种分析范式"的能力…...

编程日记 2025/8/5 9:53:33

[Swift]Xcode模拟器无法请求http接口问题

1.以前偷懒一直是这样设置 <key>NSAppTransportSecurity</key> <dict><key>NSAllowsArbitraryLoads</key><true/> </dict> 现在我在Xcode16.3上&#xff0c;这种设置方式在真机上能请求http&#xff08;应该是设备开启了开发者模式…...

编程日记 2025/8/5 4:49:34

kafka认证部署

首先启动 zookeeper /home/kafka/bin/zookeeper-server-start.sh /home/kafka/config/zookeeper.properties 创建SCRAM证书 /home/kafka/bin/kafka-configs.sh --zookeeper localhost:2181 --alter --add-config SCRAM-SHA-256[iterations8192,passwordliebe],SCRAM-SHA-512[p…...

编程日记 2025/8/5 20:56:54

基于STM32中断讲解

基于STM32中断讲解 一、NVIC讲解 简介&#xff1a;当一个中断请求到达时&#xff0c;NVIC会确定其优先级并决定是否应该中断当前执行的程序&#xff0c;以便及时响应和处理该中断请求。这种设计有助于提高系统的响应速度和可靠性&#xff0c;特别是在需要处理大量中断请求的实…...

编程日记 2025/8/2 21:00:20

Java 动态代理教程（JDK 动态代理）（以RPC 过程为例）

1. 什么是动态代理 在运行时为指定的接口自动生成代理对象&#xff0c;并通过 invoke 方法增强了这些对象的功能 2. 两个核心组件 java.lang.reflect.Proxy类 这个类提供了方法&#xff1a;newProxyInstance()用来创建一个代理对象 public static Object newProxyInstance(…...

编程日记 2025/8/3 20:03:00