DAY 4
1.AcWing 850. Dijkstra求最短路 ii
考察点:堆优化Dijkstra,求最短路问题 适合于稀疏图,利用邻接表来存储
邻接表不需要对重边做特殊的处理
(1)基础知识
时间复杂度分析:
堆优化Dijkstra
堆优化版Dijkstra与朴素版的区别主要就是在用寻找最小距离t时采用堆的方式来实现。堆其实看做是一种完全二叉树的数组对象,是最高效的优先级队列,分为小根堆和大根堆。
堆的实现方式:
手写堆 | 优先队列 |
n个数,方便插入和修改一个数 | 不支持修改任意一个数,实现方式是冗余 m个数,但是两种方式的时间复杂度相同 |
优先队列:(可以解决一些贪心问题,以及Dijkstra的优化问题)
1. priority_queue(优先队列),底层是用堆的数据结构来实现,队首元素为队列中优先级最高的一个,在插入数据时,采用冗余的实现方式,优先队列底层的数据结构堆(heap)会随时调整结构。
2. 使用时需要添加#include<queue>,using namespace std;
其定义写法为priority_queue<typename>name;
3. 优先队列只能通过top()函数来访问队首元素,优先级最高(堆顶元素),没有front(),back()函数,具有push(),top(),empty().q.size();
4. 队列内优先级设置:priority_queue<int,vector<int>,less<int>>q
队首是优先级最高的,参数2 vector<int>是承载底层数据结构堆的容器,可以根据类型修改vector的数据类型,参数3是对第一个参数的比较类,less<int>表示数字大的优先级越大(大根堆),great<int>表示数字小的优先级越大(小根堆)
最终题解代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65#include<iostream> #include<queue> #include<cstring> #include<algorithm> using namespace std; typedef pair<int,int>PII;//第一个参数存储距离起点的距离,第二个参数存储是第几个数 const int N = 1e6+10; int n, m; int h[N],e[N],ne[N],w[N],idx;//为稀疏图,所以采用邻接表来存储,w[N]为权重 int dist[N];//用于记录每一个点距离第一个点的距离 bool st[N];//用于记录该点的最短距离是否已经确定 void add(int a,int b,int c) { e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++; } int Dijkstra() { memset(dist, 0x3f,sizeof dist); //初始化距离 0x3f代表无限大 dist[1] = 0;//第一个点到自身的距离为0 priority_queue<PII,vector<PII>,greater<PII>> heap;//采用小根堆 heap.push({0,1}); while(heap.size()) { auto t = heap.top(); heap.pop(); int ver = t.second, distance = t.first;//以t为中转站,依次更新每个点所到相邻的点路径值 if (st[ver]) continue; st[ver] = true;//遍历t for(int i = h[ver]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] > dist[ver] + w[i]) { dist[j] = dist[ver] + w[i]; heap.push({dist[j], j}); } } } if(dist[n]==0x3f3f3f3f) return -1; //如果第n个点路径为无穷大即不存在最低路径 return dist[n]; } int main() { scanf("%d%d", &n, &m); memset(h, -1, sizeof h);//初始化邻接表 while(m--) { int a, b, c; scanf("%d%d%d", &a, &b, &c); add(a,b,c);//不需要考虑重边 } printf("%dn", Dijkstra()); return 0; }
2..AcWing 853. 有边数限制的最短路
考察点:bellman-ford(权重存在负数)
(1)bellman-ford的存储f方式非常多,可以使用邻接表,也可以使用结构体来存储图
(2)Bellman - ford 算法是求含负权图的单源最短路径的一种算法,效率较低,代码难度较小。其原理为连续进行松弛,在每次松弛时把每条边都更新一下,若在 n-1 次松弛后还能更新,则说明图中有负环,因此无法得出结果,否则就完成。
(通俗的来讲就是:假设 1 号点到 n 号点是可达的,每一个点同时向指向的方向出发,更新相邻的点的最短距离,通过循环 n-1 次操作,若图中不存在负环,则 1 号点一定会到达 n 号点,若图中存在负环,则在 n-1 次松弛后一定还会更新)
(3)bellman - ford算法的具体步骤
for n次
for 所有边 a,b,w (松弛操作)
dist[b] = min(dist[b],back[a] + w)
注意:back[] 数组是上一次迭代后 dist[] 数组的备份,由于是每个点同时向外出发,因此需要对 dist[] 数组进行备份,若不进行备份会因此发生串联效应,影响到下一个点
注:能求出来最短路的情况下是没有负权回路的(spfa),bellman-ford是可能的
(5) 时间复杂度:O(nm) 在题目中如果有对边数进行限制的时候,只能使用bellman-ford算法,其他情况下一般都可以被性能更好的算法替换。
需要注意在t对后续点进行更新的时候,需要备份,防止发生距离串联,影响边数限制。
(6)strcpy和memcpy主要有以下3方面的区别。
复制的内容不同。strcpy只能复制字符串,而memcpy可以复制任意内容,例如字符数组、整型、结构体、类等。
复制的方法不同。strcpy不需要指定长度,它遇到被复制字符的串结束符""才结束,如果空间不够,就会引起内存溢出。memcpy则是根据其第3个参数决定复制的长度。
用途不同。通常在复制字符串时用strcpy,而需要复制其他类型数据时则一般用memcpy,由于字符串是以“”结尾的,所以对于在数据中包含“”的数据只能用memcpy。
void *memcpy(void *dest,const void *src,size_t count);
函数说明:memcpy()用来拷贝src所指内容的内存前的count个字节到dest所指的内存地址上,memcpy会赋值完整的count个字节,不会因为遇到字符串结束''而结束
最终解题代码:
注:为什么是dist[n]>0x3f3f3f3f/2, 而不是dist[n]>0x3f3f3f3f
5号节点距离起点的距离是无穷大,利用5号节点更新n号节点距离起点的距离,将得到109−2109−2, 虽然小于109109, 但并不存在最短路,(在边数限制在k条的条件下)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48#include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N = 510,M = 10010; struct Edge { int a,b,c; }edges[M];//把每个边保存下来,将自定义的结构体放入到数组中方便维护 int dist[N]; int last[N];//备份数据防止串联 int n,m,k;//k代表最多限制经过k条边 void bellman_ford() { memset(dist, 0x3f, sizeof dist);//初始化 dist[1] = 0; for (int i = 0; i < k; i++) //k次循环 { memcpy(last, dist, sizeof dist);//备份未更新前的数据 for (int j = 0; j < m; j++) //遍历所有边 { auto e = edges[j]; dist[e.b] = min(dist[e.b], last[e.a] + e.c); //使用back:避免给a更新后立马更新b, 这样b一次性最短路径就多了两条边出来 } } } int main() { scanf("%d%d%d", &n, &m, &k); for (int i = 0; i < m; i++) { int a, b, c; scanf("%d%d%d", &a, &b, &c); edges[i] = {a, b, c}; } bellman_ford(); if (dist[n] > 0x3f3f3f3f / 2) puts("impossible"); else printf("%dn", dist[n]); return 0; }
最后
以上就是苗条诺言最近收集整理的关于2023秋招算法题每日学习(4)的全部内容,更多相关2023秋招算法题每日学习(4)内容请搜索靠谱客的其他文章。
发表评论 取消回复