拓扑排序Topological sorting/DFS C++应用例题P1113 杂务
拓扑排序
拓扑排序可以对DFS的基础上做变更从而达到想要的排序效果。因此,我们需要xy准备,vis数组记录访问状态,每一个任务都可以在dfs的过程中完成。
在使用拓扑排序方法时一些规定:
- 通常使用一个零时栈
- 不会直接输出排序的节点
- 而是递归相邻的所有节点然后入栈
- 最后输出排序后的所有节点顺序
P1113 杂务
题面
题目描述
John 的农场在给奶牛挤奶前有很多杂务要完成,每一项杂务都需要一定的时间来完成它。比如:他们要将奶牛集合起来,将他们赶进牛棚,为奶牛清洗乳房以及一些其它工作。尽早将所有杂务完成是必要的,因为这样才有更多时间挤出更多的牛奶。
当然,有些杂务必须在另一些杂务完成的情况下才能进行。比如:只有将奶牛赶进牛棚才能开始为它清洗乳房,还有在未给奶牛清洗乳房之前不能挤奶。我们把这些工作称为完成本项工作的准备工作。至少有一项杂务不要求有准备工作,这个可以最早着手完成的工作,标记为杂务 1。
John 有需要完成的 n 个杂务的清单,并且这份清单是有一定顺序的,杂务 k (k>1) 的准备工作只可能在杂务 1 至 k−1 中。
写一个程序依次读入每个杂务的工作说明。计算出所有杂务都被完成的最短时间。当然互相没有关系的杂务可以同时工作,并且,你可以假定 John 的农场有足够多的工人来同时完成任意多项任务。
输入格式
第1行:一个整数 n (3≤n≤10,000),必须完成的杂务的数目;
第 2 至 n+1 行,每行有一些用空格隔开的整数,分别表示:
- 工作序号(保证在输入文件中是从 1 到 n 有序递增的);
- 完成工作所需要的时间 len (1≤len≤100);
- 一些必须完成的准备工作,总数不超过 100 个,由一个数字 0 结束。有些杂务没有需要准备的工作只描述一个单独的 0。
保证整个输入文件中不会出现多余的空格。
输出格式
一个整数,表示完成所有杂务所需的最短时间。
输入输出样例
输入 #1
7 1 5 0 2 2 1 0 3 3 2 0 4 6 1 0 5 1 2 4 0 6 8 2 4 0 7 4 3 5 6 0
输出 #1
23
题解
如果要知道vis[i],就要求解引向它的结点。所以将其反向建边,进行记忆化搜索。枚举每个结点进行dfs。
记忆化搜索步骤如下:
•如果vis 有值则直接返回
•遍历其来源结点
•取最大值加上自己时间
•缓存并返回
代码
#include<bits/stdc++.h>
using namespace std;
#define MAXN 10010
int n, ans, len[MAXN], vis[MAXN];
// len 是任务时长,vis 从 1 结点到这个结点的最短时间
vector <int> p[MAXN];int dfs(int x) {if (vis[x]) return vis[x]; // 如果之前计算过结果就直接返回for (int i=0;i<p[x].size();i++) // 枚举 x 连出的每个边vis[x] = max(vis[x], dfs(p[x][i])); // 比较这个对应结点的值会不会更大。递归计算vis[x] += len[x]; // 要加上 x 结点自己的任务时间return vis[x];
}int main() {cin >> n;for (int i = 1; i <= n; i++) { //复杂度O(n)int x, y;cin >> x >> len[x];while (cin >> y)if (!y)break;elsep[y].push_back(x); // 连 y->x 边}for (int i = 1; i <= n; i++)ans = max(ans, dfs(i)); // 计算结点 i 开始的结果,看看会不会更优cout << ans;return 0;
}
相关文章:
拓扑排序Topological sorting/DFS C++应用例题P1113 杂务
拓扑排序 拓扑排序可以对DFS的基础上做变更从而达到想要的排序效果。因此,我们需要xy准备,vis数组记录访问状态,每一个任务都可以在dfs的过程中完成。 在使用拓扑排序方法时一些规定: 通常使用一个零时栈不会直接输出排序的节点…...

基于jenkins构建生成CICD环境
目录 一、安装配置jenkins 1、环境配置 2、软件要求 3、jdk安装(我是最小化安装,UI自带java要先删除rm -rf /usr/local/java 4、安装jenkins-2.419-1.1 二、Jenkins配置 1、修改jenkins初始密码 2、安装 Jenkins 必要插件 3、安装 Publish Over SS…...

在线图片怎么转换成PDF?在线图片转换成PDF步骤介绍
文件格式要转化不知道怎么办?想要网上下载文件格式转换软件,但是却不知道下载哪个好?今天小编小编就给大家分享一下靠谱的小圆象PDF转换器工具,想知道这款软件好不好用?在线图片怎么转换成PDF?那就进来看看吧。 在线图片怎么转换成PDF 小圆象PDF转换…...

Linux共享库基础及实例
共享库是将库函数打包成一个可执行文件,使得其在运行时可以被多个进程共享。 目标库 回顾下构建程序的一种方式: 将每个源文件编译成目标文件,再通过链接器将这些目标文件链接组成一个可执行程序。 gcc -g -c prog.c mod1.c mod2.c gcc -g …...

java八股文面试[java基础]——final 关键字作用
为什么局部内部类和匿名内部类只能访问final变量: 知识来源 【基础】final_哔哩哔哩_bilibili...

Redis 分布式锁存在什么问题 ?如何解决 ?
目录 1. 如何实现分布式锁 2. Redis 分布式锁存在什么问题 2.1 解决死锁问题 2.2 解决锁误删问题 1. 如何实现分布式锁 Redis 天生就可以作为一个分布式系统来使用,所以它实现的锁都是分布式锁。 Redis 可以通过 setnx(set if not exists)…...

n5173b是德科技keysight N5173B信号发生器
产品概述 是德科技/安捷伦N5173B EXG模拟信号发生器 当您需要平衡预算和性能时,是德科技N5173B EXG微波模拟信号发生器是经济高效的选择。它提供解决宽带滤波器、放大器、接收机等参数测试的基本信号。执行基本LO上变频或CW阻塞,低成本覆盖13、20、31.…...
React源码解析18(10)------ 实现多节点的Diff算法
摘要 在上一篇中,实现了多节点的渲染。但是之前写得diff算法,只能适用于单节点的情况,例如这种情况: <div><p><span></span></p> </div>如果对于多节点的情况: <ul><…...
Linux指令篇!
Linux 是一个广泛使用的开源操作系统,以下是一些常用的 Linux 知识点和指令: 1. 文件和目录操作: - ls:列出目录内容 - cd:切换目录 - pwd:显示当前工作目录 - mkdir:创建目录 - touch…...
Vue2学习笔记のVue组件化编程
目录 Vue组件化编程非单文件组件基本使用几个注意点组件的嵌套VueComponent一个重要的内置关系 单文件组件index.htmlmain.jsApp.vueSchool.vueStudent.vue 各位小伙伴们好呀,不知道上一篇文章你是否有收获!这篇是Vue2学习笔记第二篇,也是Vue…...

跨境电商儿童沙画办理EN71测试标准
儿童沙画就是小孩子玩的那种用彩色沙子或者彩色墨水,在有图形轮廓的纸片上去绘画,可以按照儿童沙画底板上的人物轮廓线条,动物线条,风景线条,动漫线条,去添加自己喜欢的颜色,让单调的线条变成自…...

chrome浏览器账号密码输入框自动填充时背景色不变
处理前 使用延时的方式解决 .login-box input,password:-webkit-autofill .login-box input,password:-webkit-autofill:hover, .login-box input,password:-webkit-autofill:focus, .login-box input,password:-webkit-autofill:active {-webkit-transition-delay: 999999…...

【ARM】Day9 cortex-A7核I2C实验(采集温湿度)
1. 2、编写IIC协议,采集温湿度值 iic.h #ifndef __IIC_H__ #define __IIC_H__ #include "stm32mp1xx_gpio.h" #include "stm32mp1xx_rcc.h" #include "led.h" /* 通过程序模拟实现I2C总线的时序和协议* GPIOF ---> AHB4* I2C1_S…...

【Leetcode】移动零
移动零 题目描述算法描述编程代码 链接: 移动零 题目描述 算法描述 编程代码 class Solution { public:void moveZeroes(vector<int>& nums) {//题目要求不可以复制数组,开辟额外空间int dest -1,curr 0;for(;curr < nums.size();curr){if(nums[cu…...

数据结构入门 — 顺序表详解
前言 数据结构入门 — 顺序表详解 博客主页链接:https://blog.csdn.net/m0_74014525 关注博主,后期持续更新系列文章 文章末尾有源码 *****感谢观看,希望对你有所帮助***** 文章目录 前言一、顺序表1. 顺序表是什么2. 优缺点 二、概念及结构…...

SimpleCG绘图函数(9)--绘制各种线条
一、所有线段函数概述 可填充图形绘制函数都介绍完了,还有一些特殊线条的绘制将在本篇进行讲解。所有特殊线条函数如下所示,其中还有一个区域填充函数floodfill比较特殊,是配合线条函数使用的: //绘制一系列折线段 //折线段以一组…...

RISCV 6 RISC-V加载存储指令
RISCV 6 RISC-V加载存储指令 1 RV32I Load and Store Instructions1.1 LOAD instructions1.1.1 加载指令的指令格式1.1.2 加载指令在使用时需要注意的点 1.2 STORE instructions1.2.1 存储指令的指令格式1.2.2 存储指令在使用时需要注意的点 2 RV64 Load and Store Instruction…...
木叶飞舞之【机器人ROS2】篇章_第二节、turtlebot3安装
没有真实小车的情况下,利用gazebo的仿真,操作小乌龟来学习ros2。废话不多说,直接上命令。 Install Gazebo sudo apt install ros-humble-gazebo-*Install Cartographer 假如前一节未安装源码版本的cartographer,那就安装apt版本…...

【论文阅读】自动驾驶安全的研究现状与挑战
文章目录 摘要1.引言1.1.自动驾驶安全1.2.攻击面1.3.内容和路线图 2.自动驾驶技术2.1.组成2.2.技术 3.传感器安全3.1.照相机3.2.GNSS(全球导航系统)/IMU(惯性测量单元)3.3.超声波传感器3.4.毫米波雷达3.5.激光雷达3.6.多传感器交叉…...

标签打印小工具 选择图片打印,按实际尺寸打印。可旋转图片
您可以尝试使用以下标签打印工具: 柯尼卡美能达标签打印机:功能齐全、易于使用的打印机,支持各种标签尺寸和类型。 赛门铁克标签打印机:高速打印、可靠性强的打印机,支持多种操作系统和软件。 齐柏林标签打印机&…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战
前言 现在我们有个如下的需求,设计一个邮件发奖的小系统, 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式(Decorator Pattern)允许向一个现有的对象添加新的功能,同时又不改变其…...

51c自动驾驶~合集58
我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留,CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制(CCA-Attention),…...
C++中string流知识详解和示例
一、概览与类体系 C 提供三种基于内存字符串的流,定义在 <sstream> 中: std::istringstream:输入流,从已有字符串中读取并解析。std::ostringstream:输出流,向内部缓冲区写入内容,最终取…...
Python如何给视频添加音频和字幕
在Python中,给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加,包括必要的代码示例和详细解释。 环境准备 在开始之前,需要安装以下Python库:…...

用docker来安装部署freeswitch记录
今天刚才测试一个callcenter的项目,所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

蓝桥杯3498 01串的熵
问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798, 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...

听写流程自动化实践,轻量级教育辅助
随着智能教育工具的发展,越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式,也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建,…...

c++第七天 继承与派生2
这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分:派生类构造函数与析构函数 当创建一个派生类对象时,基类成员是如何初始化的? 1.当派生类对象创建的时候,基类成员的初始化顺序 …...
Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成
一个面向 Java 开发者的 Sring-Ai 示例工程项目,该项目是一个 Spring AI 快速入门的样例工程项目,旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计,每个模块都专注于特定的功能领域,便于学习和…...

《信号与系统》第 6 章 信号与系统的时域和频域特性
目录 6.0 引言 6.1 傅里叶变换的模和相位表示 6.2 线性时不变系统频率响应的模和相位表示 6.2.1 线性与非线性相位 6.2.2 群时延 6.2.3 对数模和相位图 6.3 理想频率选择性滤波器的时域特性 6.4 非理想滤波器的时域和频域特性讨论 6.5 一阶与二阶连续时间系统 6.5.1 …...