小毅儿

最短路&...

BFS(1) DFS(4) DP(5) Huffman树(1) 动态规划(4) 埃氏筛(3) 数论(2) 未归档(24) 模版专项(9) 矩阵快速幂(3) 笔记(2) 笔记（STL）(5) 笔记（博弈）(1) 笔记（字符串）(8) 笔记（定义最大数）(1) 笔记（并查集）(2) 笔记（排列组合）(2) 笔记（结构体）(2) 笔记（范围问题）(1) 笔记（贪心）(1) 笔记（高精度）(6) 线性基(1) 组合数学(11) 题解(34)

/ 注册

全部文章 / 最短路&&最小生成树（共11篇）

换教室（Floyd+DP求期望）来自专栏

例题连接：https://ac.nowcoder.com/acm/problem/16428 /*少说话，多做事*/ #include <cstdio> #include <cstring> #include <string> #include <cmath...

2020-10-02

0 473

烽火台（SDNU1030）（SPFA）

#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #...

2020-09-20

0 558

SPFA算法模版，求单源最短路，可以有负环来自专栏

算法优点：1.时间复杂度比普通的Dijkstra和floyd低2.能够计算负权图问题3.能够判断是否有负环针对输入和输出的不同分为多个模版，虽然这些东西都是可以随时调的。第一个模版：输入：先输入点，后输入边，再输入查询个数例题链接：https://ac.nowcoder.com/acm/...

2020-09-11

0 559

一个人的旅行（Dijkstra/SPFA)

//这道题可以用迪杰特斯拉算法做，但是这道题我用的是SPFA算法， //记录一下关于链式向前星、spfa算法是怎么操作的， //spfa算法相比于迪杰特斯拉算法有很多优点，大家可以从网上搜索，很容易找到。例题链接：https://vjudge.net/problem/HDU-2066 #inc...

2020-09-11

0 829

Forsake喜欢独一无二的数（最小生成树、并查集）

试题链接：https://ac.nowcoder.com/acm/contest/1221/H /* 思路：（1）将边从大到小排序（2）对于相同权值的边统一考虑，若这条边上两点不连通开始全部加入ans中，然后再考虑重复加入的情况，也是逐渐加入这些权值相同的边，若两点不连通 ans-=w；...

2020-09-09

0 406

Kruskal算法（最小生成树）

最小生成树kruskal求法：对边权排序之后，用并查集去链接集合，直到剩下一个集合结束 kruskal算法： //第一步：给所有边按照从小到大的顺序排列 //知识点：联通分量的概念： //（1）在无向图中，如果顶点Vi到顶点Vj有路径，则称顶点Vi和Vj联通 //（2）如果无向图中任意两个顶点之间...

2020-09-03

0 506

畅通工程（并查集）

注意事项：1.用到结构体进行比较，在比较过程中for循环是以输入的道路条数为界限。2.使用并查集的时候，一定要注意m,n的使用，该用m就用m,该用n就用n。 #include <cstdio> #include <iostream> #include <cstring&...

2019-11-25

0 485

最短路（Floyd）

例题链接（这道题也可以用Dijkstra做）：https://vjudge.net/contest/341090#problem/A Floyd的优点：1.代码短2.可以带负值3.最后mp[i][j]存的是从i到j的最短路,并不是单源最短路缺点：三层for循环，时间复杂度是O（n^3)，比Dijk...

2019-11-25

0 453

Dijkstra算法、Floyd算法的区别与联系

首先，Dijkstra算法与Floyd算法都是广度优先搜索的算法。都可以用来求单源点到其他所有点的最短路径。（即从一个点到任意一个点的最短距离） 1.Dijkstra是不能计算负权图的。 Dijkstra算法本质上是贪心算法，下一条路径都是由当前更短的路径派生出来的更长的路径。不存在回溯的过程。...

2019-11-25

0 2330

Dijkstra基础用法来自专栏

例题链接：https://vjudge.net/contest/341090#problem/A Dijkstra算法：缺点：图中不存在负权边记录一下大体思路，便于复习：1.按照题目输入变量，进行初始化（标记点第一个点是false，第一个点到其它点的距离。。。）2.Dijkstra几个注意事项：（...

2019-11-25

0 671