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

拓扑排序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的基础上做变更从而达到想要的排序效果。因此&#xff0c;我们需要xy准备&#xff0c;vis数组记录访问状态&#xff0c;每一个任务都可以在dfs的过程中完成。 在使用拓扑排序方法时一些规定&#xff1a; 通常使用一个零时栈不会直接输出排序的节点…...

基于jenkins构建生成CICD环境

目录 一、安装配置jenkins 1、环境配置 2、软件要求 3、jdk安装&#xff08;我是最小化安装&#xff0c;UI自带java要先删除rm -rf /usr/local/java 4、安装jenkins-2.419-1.1 二、Jenkins配置 1、修改jenkins初始密码 2、安装 Jenkins 必要插件 3、安装 Publish Over SS…...

在线图片怎么转换成PDF?在线图片转换成PDF步骤介绍

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

Linux共享库基础及实例

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

java八股文面试[java基础]——final 关键字作用

为什么局部内部类和匿名内部类只能访问final变量&#xff1a; 知识来源 【基础】final_哔哩哔哩_bilibili...

Redis 分布式锁存在什么问题 ?如何解决 ?

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

n5173b是德科技keysight N5173B信号发生器

产品概述 是德科技/安捷伦N5173B EXG模拟信号发生器 当您需要平衡预算和性能时&#xff0c;是德科技N5173B EXG微波模拟信号发生器是经济高效的选择。它提供解决宽带滤波器、放大器、接收机等参数测试的基本信号。执行基本LO上变频或CW阻塞&#xff0c;低成本覆盖13、20、31.…...

React源码解析18(10)------ 实现多节点的Diff算法

摘要 在上一篇中&#xff0c;实现了多节点的渲染。但是之前写得diff算法&#xff0c;只能适用于单节点的情况&#xff0c;例如这种情况&#xff1a; <div><p><span></span></p> </div>如果对于多节点的情况&#xff1a; <ul><…...

Linux指令篇!

Linux 是一个广泛使用的开源操作系统&#xff0c;以下是一些常用的 Linux 知识点和指令&#xff1a; 1. 文件和目录操作&#xff1a; - ls&#xff1a;列出目录内容 - cd&#xff1a;切换目录 - pwd&#xff1a;显示当前工作目录 - mkdir&#xff1a;创建目录 - touch…...

Vue2学习笔记のVue组件化编程

目录 Vue组件化编程非单文件组件基本使用几个注意点组件的嵌套VueComponent一个重要的内置关系 单文件组件index.htmlmain.jsApp.vueSchool.vueStudent.vue 各位小伙伴们好呀&#xff0c;不知道上一篇文章你是否有收获&#xff01;这篇是Vue2学习笔记第二篇&#xff0c;也是Vue…...

跨境电商儿童沙画办理EN71测试标准

儿童沙画就是小孩子玩的那种用彩色沙子或者彩色墨水&#xff0c;在有图形轮廓的纸片上去绘画&#xff0c;可以按照儿童沙画底板上的人物轮廓线条&#xff0c;动物线条&#xff0c;风景线条&#xff0c;动漫线条&#xff0c;去添加自己喜欢的颜色&#xff0c;让单调的线条变成自…...

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协议&#xff0c;采集温湿度值 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) {//题目要求不可以复制数组&#xff0c;开辟额外空间int dest -1,curr 0;for(;curr < nums.size();curr){if(nums[cu…...

数据结构入门 — 顺序表详解

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

SimpleCG绘图函数(9)--绘制各种线条

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

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安装

没有真实小车的情况下&#xff0c;利用gazebo的仿真&#xff0c;操作小乌龟来学习ros2。废话不多说&#xff0c;直接上命令。 Install Gazebo sudo apt install ros-humble-gazebo-*Install Cartographer 假如前一节未安装源码版本的cartographer&#xff0c;那就安装apt版本…...

【论文阅读】自动驾驶安全的研究现状与挑战

文章目录 摘要1.引言1.1.自动驾驶安全1.2.攻击面1.3.内容和路线图 2.自动驾驶技术2.1.组成2.2.技术 3.传感器安全3.1.照相机3.2.GNSS&#xff08;全球导航系统&#xff09;/IMU&#xff08;惯性测量单元&#xff09;3.3.超声波传感器3.4.毫米波雷达3.5.激光雷达3.6.多传感器交叉…...

标签打印小工具 选择图片打印,按实际尺寸打印。可旋转图片

您可以尝试使用以下标签打印工具&#xff1a; 柯尼卡美能达标签打印机&#xff1a;功能齐全、易于使用的打印机&#xff0c;支持各种标签尺寸和类型。 赛门铁克标签打印机&#xff1a;高速打印、可靠性强的打印机&#xff0c;支持多种操作系统和软件。 齐柏林标签打印机&…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

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

51c自动驾驶~合集58

我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留&#xff0c;CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制&#xff08;CCA-Attention&#xff09;&#xff0c;…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

用docker来安装部署freeswitch记录

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

蓝桥杯3498 01串的熵

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

听写流程自动化实践,轻量级教育辅助

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

c++第七天 继承与派生2

这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分&#xff1a;派生类构造函数与析构函数 当创建一个派生类对象时&#xff0c;基类成员是如何初始化的&#xff1f; 1.当派生类对象创建的时候&#xff0c;基类成员的初始化顺序 …...

Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成

一个面向 Java 开发者的 Sring-Ai 示例工程项目&#xff0c;该项目是一个 Spring AI 快速入门的样例工程项目&#xff0c;旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计&#xff0c;每个模块都专注于特定的功能领域&#xff0c;便于学习和…...

《信号与系统》第 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 …...