图论入门题题解

news/2024/4/19 14:49:28/文章来源:https://blog.csdn.net/2301_79293429/article/details/136565883

✨欢迎来到脑子不好的小菜鸟的文章✨

      🎈创作不易,麻烦点点赞哦🎈

          所属专栏:刷题_脑子不好的小菜鸟的博客-CSDN博客

          我的主页:脑子不好的小菜鸟

          文章特点:关键点和步骤讲解放在

          代码相应位置

拓扑排序 / 家谱树
https://vjudge.net/contest/613618#problem/A


//拓扑排序:找到入度为0的点,将其写入答案,再删去其箭头,再继续找入度为0的点,循环往复vector<int>edeg[101];
int n, deg[101] = { 0 };//入度
void init()//建图
{cin >> n;int i, val;for (i = 1; i <= n; i++){while (cin >> val && val != 0){edeg[i].push_back(val);deg[val]++;}}
}void toposort()//拓扑排序
{int i;queue<int> que;for (i = 1; i <= n; i++){if (deg[i] == 0){cout << i << ' ';que.push(i);}}while (!que.empty()){int t = que.front();que.pop();for (int i : edeg[t])//相当于i表示edeg[t]的第一个元素,进行一次循环后就是第二个元素,循环往复{deg[i]--;if (deg[i] == 0){cout << i << ' ';que.push(i);//push的原因:可能i(也就是edeg[t])还有箭头指向其他的数,也就是后面辈分比它小的,要通过i来找比它辈分小的}}}
}int main()
{init();//建图toposort();//拓扑排序return 0;
}

P3371 【模板】单源最短路径(弱化版)
https://www.luogu.com.cn/problem/P3371

///*法一:邻接矩阵*/
占的空间较多,时间复杂度较大,不适合/*法二:结构体,堆优化*/
//要一个结构体,存一个点相关的东西(to, wei, next)(终点, 权值, 下一个儿子)
//cnt:结构体下标
//head[MAX]:head[i]:查找i点的第一个儿子
//pos:将被标记的值
//ans[MAX]:最短距离
//visit[MAX]:是否被标记过//题解:https://www.luogu.com.cn/article/oswxjzrl
#include <iostream>#include <climits>
using namespace std;
const int MAX = 1e6;int cnt;//结构体下标int visit[MAX];//标记int n, m, s;int head[MAX];//存放儿子int ans[MAX];//放到起点的最短距离
struct EDGE
{int wei;//权值int to;//目的地int next;//下一个儿子
}edge[MAX];
void add(int u, int v, int w){cnt++;edge[cnt].wei = w;edge[cnt].to = v;edge[cnt].next = head[u];//将下一个儿子记录head[u] = cnt;//更新第一个儿子
}
int main(){cin >> n >> m >> s;int i;//初始化ansfor (i = 1; i <= n; i++)ans[i] = INT_MAX;ans[s] = 0;int u, v, w;for (i = 1; i <= m; i++){cin >> u >> v >> w;add(u, v, w);}int pos = s;//初始化pos为swhile (visit[pos] == 0){int minn = INT_MAX;//注意更新visit[pos] = 1;//标记//更新儿子的最短路径for (i = head[pos]; i != 0; i = edge[i].next){if (visit[edge[i].to] == 0 && ans[edge[i].to] > ans[pos] + edge[i].wei)ans[edge[i].to] = ans[pos] + edge[i].wei;}//找最短路径for (i = 1; i <= n; i++){if (visit[i] == 0 && ans[i] < minn){minn = ans[i];pos = i;}}}for (i = 1; i <= n; i++)cout << ans[i] << ' ';cout << endl;return 0;
}

P4779 【模板】单源最短路径(标准版)
https://www.luogu.com.cn/problem/P4779

注意:该题用上一题的代码会超时,因此要用堆优化,也就是优先队列

//友情提示:正权图  请  使用dijkstra算法,   负权图  请  使用SPFA算法//弱化版的代码超时---->要用堆优化
/*
核心:priority_queue< pair<int,int> > 用优先队列来取最近的点,就不用遍历找点了在pq中,是按pair的第一个元素(first)由大到小排序的,所以pair<距离,点号>,注意因为要的是最小值,所以距离要存负值
其实距离是纯纯的工具人,我们只是需要它来维持点的排序每次取队首h,取出的就是dis最短的点
还要注意:
如果这个点的dis不等于h的dis,说明这个点在入队之后被更新了,那么我们就不用这个点了,直接continue;
因为后面会有个h2点比h1的dis更小,用h1更新就没有意义了
*///使用优先队列,注意:优先队列是从大到小排列,所以存进去应该存负数C代码:
#include <queue>
/*堆优化:利用优先队列,降低复杂度,直接排序,注意优先队列是由大到小排列的,因此距离是负数 */
#include <climits>
#include <iostream>using namespace std;const int MAX = 1e6;
int n, m, s;
int ans[MAX];
int cnt;
int head[MAX];
int visit[MAX];struct EDGE
{int to;int next;int wei;
}edge[MAX];void add(int u, int v, int w)
{cnt++;edge[cnt].wei = w;edge[cnt].to = v;edge[cnt].next = head[u];head[u] = cnt;
}int main()
{int i;int u, v, w;cin >> n >> m >> s;for (i = 1; i <= n; i++)ans[i] = INT_MAX;ans[s] = 0;for (i = 1; i <= m; i++){cin >> u >> v >> w;add(u, v, w);}priority_queue<pair<int, int> >que;//距离,点que.push({0, s});while (!que.empty()){int qh = que.top().first;int h = que.top().second;que.pop();/*记得pop()!!!!!!!!!*/if (visit[h] == 0){visit[h] = 1;for (i = head[h]; i != 0; i = edge[i].next)//不断找下一个儿子,直到找完{if (ans[edge[i].to] > ans[h] + edge[i].wei){ans[edge[i].to] = ans[h] + edge[i].wei;if (visit[edge[i].to] == 0)que.push({ -ans[edge[i].to], edge[i].to });}}}}for (i = 1; i <= n; i++)cout << ans[i] << ' ';cout << endl;return 0;
}

B3647 【模板】Floyd
https://www.luogu.com.cn/problem/B3647 

//floyd算法
//要注意中转点,可以直接i到j,也可以i->k,k->j,因此要比较两个数据的大小,最后表中的是最短路径
//注意是无向图#include <climits>int main()
{int n, m, i, j, u, v, w;long long board[105][105] = { 0 };//存最短路径cin >> n >> m;for (i = 1; i <= n; i++){for (j = 1; j <= n; j++){if (i == j)board[i][j] = 0;elseboard[i][j] = INT_MAX;}}for (i = 1; i <= m; i++){cin >> u >> v >> w;if (w < board[u][v])board[u][v] = w;if (w < board[v][u])board[v][u] = w;}int k;           for (k = 1; k <= n; k++)//把k当中转点,注意是放在i,j循环的外面{for (i = 1; i <= n; i++)//行,列{if (i == k)continue;for (j = 1; j <= n; j++){if (j == k)continue;if (i == j)continue;if (board[i][k] != INT_MAX && board[k][j] != INT_MAX)board[i][j] = min(board[i][j], board[i][k] + board[k][j]);}}}for (i = 1; i <= n; i++){for (j = 1; j <= n; j++){cout << board[i][j] << ' ';}cout << endl;}return 0;
}

恭喜你啦,今天又进步了一点点~

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_999057.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

vscode setting.json 全局设置 工作区设置 位置 优先级

vscode中setting.json有两种配置权限 一、全局配置&#xff1a;setting.json文件位于C:\Users\Administrator\AppData\Roaming\Code\User\settings.json 二、工作区配置&#xff1a;setting.json文件位于工作区的.vscode\settings.json 当两种配置同时存在时&#xff0c;工作区…

<商务世界>《第9课 产品地图》

1 产品地图 产品地图的核心是产品或用户的业务流程或地图导航&#xff0c;从用户和产品两条路线出发&#xff0c;搭建业务架构&#xff0c;并划分明确的功能模块&#xff0c;用图形化方式记录、整理、表现出产品的清晰特点。其中&#xff0c;包括用户在使用过程中做了什么、感…

计算机网络-网络应用服务器

1.网络操作系统&#xff1a; 用统一的方法管理各主机之间的通信和资源的共享。主要功能&#xff1a;网络通信、共享资源、网络管理、网络服务、互操作、网络接口。四大特征&#xff1a;并发、资源共享、虚拟、异步性。安全性&#xff1a;用户账号、时间限制、地点限制、磁盘空间…

【数据结构】单链表的层层实现!! !

关注小庄 顿顿解馋(●’◡’●) 上篇回顾 我们上篇学习了本质为数组的数据结构—顺序表&#xff0c;顺序表支持下标随机访问而且高速缓存命中率高&#xff0c;然而可能造成空间的浪费&#xff0c;同时增加数据时多次移动会造成效率低下&#xff0c;那有什么解决之法呢&#xff…

特种车日常检修VR虚拟互动培训软件节省大量的教学资源和成本

随着科技的不断发展&#xff0c;虚拟现实(VR)技术已经逐渐融入了各行各业&#xff0c;其中特种车辆的养护教学也从中受益匪浅。VR虚拟仿真教学在特种车辆养护领域的应用&#xff0c;不仅创新了教学方式&#xff0c;还为提高学员的学习效果和实际操作技能提供了强有力的支持。 特…

c# combox 行间距调整

初始化combox comboBox1.DropDownStyle ComboBoxStyle.DropDownList;comboBox1.ItemHeight 25; // 设置 combox 的行高comboBox1.DrawMode DrawMode.OwnerDrawVariable; 添加 DrawItem 事件 private void comboBox1_DrawItem(object sender, DrawItemEventArgs e){if (…

ArrayList常用API

常见方法 add 增remove 删set 改get 查clear 清空元素size 长度isEmpty 为空判断 用法 // String就是泛型 这种使用方法对于限制类型很有用 ArrayList<String> arrayList new ArrayList<>();// add 添加元素 返回的是boolean 代表是否添加成功 arrayList.add(&qu…

【Neo4j系列】Neo4j之CQL语句和函数介绍

本文将对Neo4j中的CQL语句和CQL函数进行详细介绍。 作者&#xff1a;后端小肥肠 目录 1. 前言 2. CQL语句 2.1. CQL简介 2.2. CREATE命令 2.3. MATCH命令 2.4. RETURN命令 2.5. MATCH和RETURN 2.6. CREATEMATCHRETURN命令 2.7. 关系基础 2.8. CREATE创建标签 2.9. WH…

Unity 让角色动起来(动画控制器)

下载素材&#xff1a; 导入后&#xff0c;找到预制体和动画。 新建动画控制器&#xff0c;拖动到预制体的新版动画组件上。 建立动画关系 创建脚本&#xff0c;挂载到预制体上。 using System.Collections; using System.Collections.Generic; using UnityEngine;public c…

AIGC启示录:深度解析AIGC技术的现代性与系统性的奇幻旅程

✨✨ 欢迎大家来访Srlua的博文&#xff08;づ&#xffe3;3&#xffe3;&#xff09;づ╭❤&#xff5e;✨✨ &#x1f31f;&#x1f31f; 欢迎各位亲爱的读者&#xff0c;感谢你们抽出宝贵的时间来阅读我的文章。 我是Srlua小谢&#xff0c;在这里我会分享我的知识和经验。&am…

Cloud-Eureka服务治理-Ribbon负载均衡

构建Cloud父工程 父工程只做依赖版本管理 不引入依赖 pom.xml <packaging>pom</packaging><parent><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-parent</artifactId><version>2.3.9.RELEA…

【C语言】数据类型和变量

前言&#x1f49e;&#x1f49e; 啦啦啦~这里是土土数据结构学习笔记&#x1f973;&#x1f973; &#x1f4a5;个人主页&#xff1a;大耳朵土土垚的博客 &#x1f4a5; 所属专栏&#xff1a;C语言笔记 &#x1f4a5;欢迎大家&#x1f973;&#x1f973;点赞✨收藏&#x1f49…

二维码门楼牌管理系统在教育领域的应用及其优势

文章目录 前言一、二维码门楼牌管理系统概述二、教育领域的应用场景三、二维码门楼牌管理系统的优势四、结语 前言 随着信息技术的快速发展&#xff0c;二维码门楼牌管理系统在教育领域的应用越来越广泛。该系统不仅提高了地址信息的准确性&#xff0c;还为学校、家长和教育工…

分库分表

分库分表 1 分库分表介绍1.1、分库分表概述1.2、分库分表场景示例1.3、大数据存储下数据库性能分析1.4、小结 2 分库分表方式2.1、垂直分表2.2、垂直分库2.3、水平分表2.4、水平分库2.5、分库分表带来的问题2.6、分库分表小结 1 分库分表介绍 1.1、分库分表概述 分库分表本质…

k8s常用命令大全

k8s常用的命令 下面是一些常用的Kubernetes&#xff08;K8s&#xff09;命令&#xff0c;以及它们的简要说明。这些命令可以帮助您管理和操作Kubernetes集群中的资源。 集群管理命令&#xff1a; kubectl cluster-info: 显示集群的基本信息。 kubectl config use-context &l…

QT:用opencv的KNN识别图片中的LED数字(一)

前言 一款功能测试的软件demo,使用了QT作为界面,主要使用了opencv的KNN识别,使用gstreamer作为管道,用来打开图片。后期会写一篇打开摄像头实时识别的文章。 (正在写,未完成,稍候) 效果一预览: 效果二预览: 效果三预览: 正在写。。。 设计思路 1. 软件UI设计 2. …

TCP重传机制、滑动窗口、拥塞控制

一、总述 TCP&#xff0c;Transmission Control Protocol&#xff0c;是一个面向连接、基于流式传输的可靠传输协议&#xff0c;考虑到的内容很多&#xff0c;比如数据包的丢失、损坏、分片和乱序等&#xff0c;TCP协议通过多种不同的机制来实现可靠传输。今天&#xff0c;重点…

专访天谋科技谭新宇:我与 IoTDB 的这些年

从清华大学到天谋科技&#xff1a;一名 IoTDB 深度参与者的转换与成长。 自 2020 年以来&#xff0c;在数字化、国产化浪潮叠加下&#xff0c;中国信创产业得以高速发展&#xff0c;从基础硬件到基础软件、应用软件再到信息安全层面均涌现出一批领先的项目和厂商。 聚焦到基础软…

20240308-1-校招前端面试常见问题CSS

校招前端面试常见问题【3】——CSS 1、盒模型 Q&#xff1a;请简述一下 CSS 盒模型&#xff1f; W3C 模式&#xff1a;盒子宽widthpaddingbordermargin 怪异模式&#xff1a;盒子宽widthmargin Q&#xff1a;inline、block、inline-block 元素的区别&#xff1f; inline&am…

使用Go的encoding/asn1库处理复杂数据:技巧与最佳实践

使用Go的encoding/asn1库处理复杂数据&#xff1a;技巧与最佳实践 引言ASN.1 基础ASN.1与Go语言的关系ASN.1数据类型 encoding/asn1库概览主要功能和特性关键API应用场景 基本使用方法序列化&#xff08;编码&#xff09;反序列化&#xff08;解码&#xff09;处理复杂数据结构…