Blog E

路漫漫其修远兮,吾将上下而求索。

和小哥哥一起刷洛谷(7)

图论之dijkistra算法

关于dijkstra 维基百科 (动图被作者吃了) 戴克斯特拉算法(英语:Dijkstra’s algorithm,又译迪杰斯特拉算法)由荷兰计算机科学家艾兹赫尔·戴克斯特拉在1956年提出。戴克斯特拉算法使用了广度优先搜索解决赋权有向图的单源最短路径问题。该算法存在很多变体;戴克斯特拉的原始版本找到两个顶点之间的最短路径,但是更常见的变体固定了一个顶点作为源节点然后找到该顶点到图中所有其它节点的最短路径,产生一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。举例来说,如果图中的顶点表示城市,而边上的权重表示城市间开车行经的距离,该算法可以用来找到两个城市之间的最短...

和小哥哥一起刷洛谷(6)

图论之SPFA算法

关于spfa spfa伪代码: void spfa(s){ 最短路数组全部设为无限大; 队列 q; 起点s入队; s离s的距离设为零; while(队列非空){ 取出队首;弹出队首; for(int i=0;i<u的出度;i++){ v=第i个终点; w=到v的权值; if(到u点的最短路+w<目前到v点的最短路){//松弛 更新目前到v点的最短路; v入队; ...

和小哥哥一起刷洛谷(5)

图论之深度优先搜索DFS

关于dfs dfs伪代码: void dfs(s){ for(int i=0;i<s的出度;i++){ if(used[i]为真) continue; used[i]=1; dfs(i); } return; } 统计无向图的连通分量 显然,你在洛谷上是搜不到这题的,因为这是我们学校团队的题。所以还是找个小板凳专心听我讲吧。 题目描述: 给定无向图G(V,E),请统计G中连通分量的数量。 连通分量:结点V的一个子集V’,保证V’中任意两点间都有路径 需要在主循环中进行多次dfs 输入输...

和小哥哥一起刷洛谷(4)

图论之广度优先搜索BFS

关于bfs: 你怎么会连这个都不知道!!!自己好好谷歌一下!!!(其实我也刚学) bfs伪代码: while(队列非空){ 取出队首元素u; 弹出队首元素; u染色为黑色; for(int i=0;i<u的出度){ if(i非白色) continue; u的第i个出线连着的点入队; i染为灰色; } } 可爱的分割线 无权最短路 显然,你在洛谷上是搜不到这题的,因为这是我们学校团队的题。所以还是找个小板凳专心听我讲吧。 题目描述: 给定无权无向图G(V,E)和源点s/终点t,...

和小哥哥一起刷洛谷(1)

四道水题

小哥我是编程爱好者,正在学习摸索中,此文就是我最近编的代码以及编程中的思路,易错点等心得体会。 今天小哥我作为cpp党就来带大家刷几道很有意思的题目。 由于微信不支持插入代码,只能用markdown写文章,markdown的排版功能尚不熟悉,小试一下。 P1029最大公约数和最小公倍数问题 题目: 输入 2 个正整数x0,y0,求出满足下列条件的 P,Q 的个数 条件: P,Q 是正整数 要求: P,Q 以 x0 为最大公约数,以 y0 为最小公倍数. 试求:满足条件的所有可能的 2 个正整数的个数. 思路: 1.枚举a/y0的值 代码: #include<bits/s...