图论知识储备

图的存储,学会用pair,pair在排序一般先按照第一关键字排序,然后按照第二关键字排序

p,k算法求最小生成树,了解其贪心本质,学会按照其他条件贪心地求各种最大最小生成树,会求次小生成树,求最小生成树计数

正权最短路,负权最短路,会求筛点后的最短路,符合条件的最短路,spfa,dij,floyd

floyd不会比n次dij或spfa慢多少?我们还要学会。。用spfa或Bellman判断是否存在负权回路或者正权回路(最短路,最长路),核心逻辑在于。。最短路只经过n-1个点

spfa的本质是队列优化的bellman-ford,为什么要记录哪些点在队列里,因为如果一个点已经入队了。。那么它不需要再次入队。。前面与他相同的点会更新其他的点

这里有一个常见的性质。。那就是dij算法里每个点只入队1次,而spfa入队不一定是1次。。大于等于1次

所以这个记录在不在队列里。。是一个基础的优化

会求出所有的最短路。。输出方案。。以及最短路计数

会求出k短路。。用可持久堆的方法

多源最短路,Floyd-Walshal传递闭包

拓扑排序,记录入度为零,某些拓扑序问题可以用BFS,

朴素,ko,tarjan求强连通分量,缩点,完备匹配问题,与LCA等问题一起思考,考虑缩点后出度为零和入度为零等特殊点

强连通分量

左偏树=》可持久化左偏树

还有一部分网络流,最大流,最小割,费用流还没学。。

原文地址:https://www.cnblogs.com/linkzijun/p/6347858.html