知道了prim最小生成树算法，我们发现每次找距离最小的点的操作和dijkstra算法中的操作很像，所以我们考虑是否可以将迪杰的优化套到prim上，也即用优先队列时间复杂度大概是O(mlogm)例题：洛谷P3366【模板】最小生成树#include<iostream>#include<utility>#include<vector>#includ

全源最短路，顾名思义，就是任意两点之间的最短路floyed的思路就是每次选一个点k，如果k不在u和v路径上，就不改变，如果k在u和v的路径上，进行松弛操作d[u][v]=min(d[u][v],d[u][k]+d[k][v])例题洛谷B3647【模板】Floyd算法#include<iostream>#defineforup(i,l,r)for(inti=l;i<=r;

单源最短路，顾名思义，就是从一个起点到其余点的最短距离Bellman-Ford算法的思路是进行至多n-1轮的更新，每次遍历所有的边，进行松弛操作d[v]=min(d[v],d[u]+w);Bellman-Ford算法可以处理有负边权的图，也可以判负环，只要在第n轮还能进行松弛操作，说明存在负环例题洛谷P3371【模板】单

就是把LCA问题转化为RMQ问题转化之前先要了解欧拉序列：对一棵树进行DFS，无论是第一次访问还是回溯，每次到达一个结点时都将编号记录下来，可以得到一个长度为2n-1的序列，这个序列被称作这棵树的欧拉序列。比如下面这个树：(2连3和4)1->2->3        ->4->5其序列就是123

例题：洛谷P3379【模板】最近公共祖先（LCA）https://www.luogu.com.cn/problem/P3379tarjan算法是利用了并查集来求LCA的，时间复杂度比倍增低，是O(n+m)#include<iostream>#include<vector>#include<utility>#defineforup(i,l,r)for(inti=l;i<=r;i++)#definefordown(i,l,r)fo