day58 第十一章:图论part08
拓扑排序精讲
关键:
先找到入度为0的节点,把这些节点加入队列/结果,然后依次循环再找。
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;
int main() {int m, n, s, t;cin >> n >> m;vector<int> inDegree(n, 0); // 记录每个文件的入度unordered_map<int, vector<int>> umap;// 记录文件依赖关系vector<int> result; // 记录结果while (m--) {// s->t,先有s才能有tcin >> s >> t;inDegree[t]++; // t的入度加一umap[s].push_back(t); // 记录s指向哪些文件}queue<int> que;for (int i = 0; i < n; i++) {// 入度为0的文件,可以作为开头,先加入队列if (inDegree[i] == 0) que.push(i);//cout << inDegree[i] << endl;}// int count = 0;while (que.size()) {int cur = que.front(); // 当前选中的文件que.pop();//count++;result.push_back(cur);vector<int> files = umap[cur]; //获取该文件指向的文件if (files.size()) { // cur有后续文件for (int i = 0; i < files.size(); i++) {inDegree[files[i]] --; // cur的指向的文件入度-1if(inDegree[files[i]] == 0) que.push(files[i]);}}}if (result.size() == n) {for (int i = 0; i < n - 1; i++) cout << result[i] << " ";cout << result[n - 1];} else cout << -1 << endl;} dijkstra(朴素版)精讲
不能处理负权重,贪心算法,minDist表示距离原点最近的距离。
跟prim一样
#include <iostream>
#include <vector>
#include <climits>
using namespace std;int main(){int n,m,s,e,v;cin>>n>>m;vector<vector<int>> grid(n+1,vector<int>(n+1, INT_MAX));for(int i=0;i<m;i++){cin>>s>>e>>v;grid[s][e]=v;}vector<bool> visited(n+1, false);vector<int> minDist(n+1, INT_MAX);int start = 1;minDist[start] = 0;for(int i=0;i<n;i++){int cur = -1;int minVal = INT_MAX;//1.选择未到过的且距离起始点最近车站for(int j=1;j<=n;j++){if(!visited[j] && minDist[j]<minVal){cur = j;minVal = minDist[j];}}if(cur == -1) {break;}//2.到达该车站visited[cur] = true;//3.更新minDistfor(int j=1;j<=n;j++){if(!visited[j] && grid[cur][j]!=INT_MAX && minDist[cur]+grid[cur][j]<minDist[j]){minDist[j] = minDist[cur]+grid[cur][j];}}// cout<<"cur="<<cur<<endl;// for(int k=1;k<=n;k++){// cout<<minDist[k]<<" ";// }// cout<<endl;}int count = 0;for(int i=1;i<=n;i++){if(visited[i]){count++;}}if(count==n){cout<<minDist[n]<<endl;}else{cout<<-1<<endl;}} 相关文章:
day58 第十一章:图论part08
拓扑排序精讲 关键: 先找到入度为0的节点,把这些节点加入队列/结果,然后依次循环再找。 #include <iostream> #include <vector> #include <queue> #include <unordered_map> using namespace std; int main() {int …...
网络安全-openssl工具
OpenSSl是一个开源项目,包括密码库和SSL/TLS工具集。它已是在安全领域的事实标准,并且拥有比较长的历史,现在几乎所有的服务器软件和很多客户端都在使用openssl,其中基于命令行的工具是进行加密、证书管理以及测试最常用到的软件。…...
Java面试第六山!《MySQL基础知识点》
一、引言 MySQL 作为一款广泛使用的开源关系型数据库管理系统,在软件开发领域占据着重要地位。无论是小型项目还是大型企业级应用,都能看到 MySQL 的身影。今天就来和大家分享 MySQL 的相关知识,帮助大家更好地应对日常开发和面试。 二、My…...
云计算中的API网关是什么?为什么它很重要?
在云计算架构中,API网关(API Gateway)是一个重要的组件,主要用于管理、保护和优化不同服务之间的接口(API)通信。简单来说,API网关就像是一个中介,它充当客户端和后端服务之间的“桥…...
【WebGL】fbo双pass案例
双pass渲染案例(离线渲染一个三角面,然后渲染到一个占满屏幕的矩阵上) 离线渲染如何需要开启深度测试的话,需要额外操作,这里不展开 <!DOCTYPE html> <html lang"en"><head><meta ch…...
Unity面板介绍_层级面板(23.1.1)
一、Inspector(检视面板) 显示当前选定游戏对象附加的组件及其属性信息。为重要游戏物体选择图标 二、面板详情...
详解Nginx 配置
一、Nginx 介绍 Nginx 是一款轻量级的 Web 服务器 / 反向代理服务器及电子邮件(IMAP/POP3)代理服务器。它由俄罗斯的程序设计师 Igor Sysoev 所开发,自 2004 年发布以来,凭借其高性能、低内存消耗、高并发处理能力等特点…...
数据库系统概念
1. 绪论 数据库的基本概念: 数据(data): 数据库中存储的基本对象, 可以是文字, 声音, 图片, 视频等。 数据库(DB): 概括来说就是永久存储, 有组织, 可共享的大量数据的集合。 数据库管理系统(DBMS): 和操作系统一样是计算机基础软件, 主要有数据定义语言(DDL, 对数据对象的组…...
51单片机学习之旅——定时器
打开软件 1与其它等于其它,0与其它等于0 1或其它等于1,0或其它等于其它 TMODTMOD&0xF0;//0xF01111 0000进行与操作,高四位保持,低四位清零,高四位定时器1,低四位定时器0 TMODTMOD|0x01;//0x010000 0…...
一台服务器将docker image打包去另一天服务器安装这个镜像
一台服务器将docker image打到去另一天服务器安装这个镜像 1. 打包2.另一台服务器执行 1. 打包 docker save -o nebula-graph-studio.tar harbor1.vm.example.lan/dockerio/vesoft/nebula-graph-studioxxx.tar 是打包好的文件 后面的是 docker image 2.另一台服务器执行 docke…...
QT串口通信之二,实现单个温湿度传感器数据的采集(采用Qt-modbus实现)
接上 QT串口通信之一,实现单个温湿度传感器数据的采集 上述文章中用QSerialPort实现了温湿度传感器的采集,实际上比较麻烦的,因为需要自定义解析帧, 接下来,用Qt-modbus-封装度更高的协议,来实现温湿度的采集; #include "MainWindow.h" #include "ui_M…...
基于SpringBoot的校园消费点评管理系统
作者:计算机学姐 开发技术:SpringBoot、SSM、Vue、MySQL、JSP、ElementUI、Python、小程序等,“文末源码”。 专栏推荐:前后端分离项目源码、SpringBoot项目源码、Vue项目源码、SSM项目源码、微信小程序源码 精品专栏:…...
【小沐学Java】VSCode搭建Java开发环境
文章目录 1、简介2、安装VSCode2.1 简介2.2 安装 3、安装Java SDK3.1 简介3.2 安装3.3 配置 4、安装插件Java Extension Pack4.1 简介4.2 安装4.3 配置 结语 1、简介 2、安装VSCode 2.1 简介 Visual Studio Code 是一个轻量级但功能强大的源代码编辑器,可在桌面上…...
《操作系统 - 清华大学》8 -4:进程管理:进程控制结构
深度剖析进程控制块:操作系统进程管理的核心关键 在操作系统的复杂体系中,进程控制块(PCB)是实现高效进程管理的关键所在。接下来,将从多个维度深入剖析进程控制块,帮助更好地理解其在操作系统中的重要作用…...
RPC 框架项目剖析
RPC 框架项目剖析 说明 本文用于梳理一个 rpc项目的实现细节,此项目基于cpp语言 大概三千行左右,用于学习目的。 项目链接:rpc项目 项目底层类 1.抽象消息类 描述: 各种消息的基类 属性: 消息id,消息类型…...
C++ Boost面试题大全及参考答案
目录 boost::thread_group 如何实现批量线程管理? 解释 boost::asio 中 proactor 模式的设计原理 使用 boost::atomic 实现无锁环形缓冲区 boost::mutex 与 std::mutex 在异常安全上的差异 如何用 boost::condition_variable 实现生产者 - 消费者模型 当 boost::shared_p…...
关于Transparent native-to-ascii conversion
1、功能 自动转换ASCII编码,即在文件系统上,文件的编码格式为ascii编码,在编辑器(idea/pycharm)中,其展现结果为配置的编码格式,仅展现方便阅读 使用UTF-8并勾选自动转换ASCII编码结果&#x…...
js数据类型检测
JavaScript的数据类型检测 typeof操作符 适用场景 基本数据类型快速判断:适用于快速判断变量是否为number、string、boolean、undefined、function等基本数据类型。比如在函数参数检查中,若要求传入数字参数,可用typeof来初步判断。函数类型…...
go 模块管理
go version 查看版本 go version go1.21.12 windows/amd64 需要保证:go的版本升级为1.11以上,go mod依赖的最底版本 go env 查看go的环境变量 go env 开启go mod # 标识开启go的模块管理 set GO111MODULE=on GO111MODULE有三个值:off, on和auto(默认值)。 GO111M…...
记一次复杂分页查询的优化历程:从临时表到普通表的架构演进
1. 问题背景 在项目开发中,我们需要实现一个复杂的分页查询功能,涉及大量 IP 地址数据的处理和多表关联。在我接手这个项目的时候,代码是这样的 要知道代码里面的 ipsList 数据可能几万条甚至更多,这样拼接的sql,必然是要内存溢出的,一味地扩大jvm参数不…...
ENVI实战:用ROI工具和外部矢量文件,5分钟搞定复杂区域的精准图像裁剪
ENVI高效裁剪实战:矢量边界与ROI工具在遥感影像处理中的精准应用 遥感影像处理中,图像裁剪是最基础却至关重要的环节。尤其当我们需要从覆盖数百平方公里的大范围影像中,精准提取出某个特定行政区划、生态保护区或流域边界时,传统…...
C++ MapViewOfFile 内存映射实战:解锁Windows大文件高效处理
1. 为什么需要内存映射技术? 如果你曾经尝试用传统方式读取几个GB的大文件,可能会遇到性能瓶颈。我做过一个实验:用fread逐块读取1GB的日志文件,耗时超过3秒;而改用内存映射方式,同样的文件仅需不到0.5秒。…...
从零开始选型:你的项目该用STM32、普通单片机还是工控机?一个真实案例说清楚
从零开始选型:你的项目该用STM32、普通单片机还是工控机?一个真实案例说清楚 在智能硬件开发的世界里,选型往往比编码更让人头疼。去年我负责一个智能农业监测系统的开发,团队争论了整整两周:用STM32、Arduino还是直接…...
“Community-Driven Spring Integration Extensions”(社区驱动的 Spring Integration 扩展)是指由 Spring 社区
“Community-Driven Spring Integration Extensions”(社区驱动的 Spring Integration 扩展)是指由 Spring 社区(而非 Spring 官方核心团队)开发、维护和贡献的一系列补充性模块,用于增强 Spring Integration 的功能边…...
计算机常用英文词汇概念解释
目录 1、property与attribute 2、run、execute与perform 3、option、item、menu、context menu 4、configuration、setting 5、parameter与 argument 6、function、feature 7、command line 8、terminal与console 9、shell ... 计算机常用英文词汇概念解释 伴随着计算机的诞生和…...
终极指南:PINRemoteImage内存管理完全解析,避免iOS应用内存泄漏的关键技巧
终极指南:PINRemoteImage内存管理完全解析,避免iOS应用内存泄漏的关键技巧 【免费下载链接】PINRemoteImage A thread safe, performant, feature rich image fetcher 项目地址: https://gitcode.com/gh_mirrors/pi/PINRemoteImage PINRemoteImag…...
企业云盘ROI计算:让你的老板心服口服
开篇一个真实故事: 某设计院信息科主任老张,连续三年向院长申请企业云盘采购预算,前两次都被驳回,理由是"看不出回报"。第三年,他带了一份12页的ROI分析报告,院长当场批准,预算比申请…...
云端全自动AI漫剧生成工作流:从模型选型到完整实现
云端全自动AI漫剧生成工作流:从模型选型到完整实现 一、绪论 1.1 漫剧产业的AI化浪潮 漫剧作为“文字故事+静态漫画+动态效果”的新型内容形态,凭借低制作成本、高传播效率的优势,正迅速成为短视频平台的流量新风口。然而,传统漫剧生产流程高度依赖人工协作——从剧本改…...
瑞萨RZN2L ADC+DMA数据流实战:从寄存器配置到双缓冲模式解析
瑞萨RZN2L ADCDMA数据流实战:从寄存器配置到双缓冲模式解析 在嵌入式开发领域,高效稳定的数据采集系统往往是项目成功的关键。当我们面对需要连续采集传感器数据的场景时,如何确保数据不丢失、系统不卡顿,就成为工程师必须解决的难…...
别再只改YAML了!手把手教你从零实现YOLOv8的MSAM注意力模块(附完整代码)
从零构建YOLOv8的MSAM注意力模块:多尺度特征融合实战指南 在目标检测领域,YOLOv8凭借其出色的速度和精度平衡成为工业界的热门选择。但当你面对复杂场景中的多尺度目标时,是否发现模型对小物体或遮挡目标的检测效果不尽如人意?传统…...
