图论-最短路-解题技巧集
图论-最短路-解题技巧集
本博客仅仅是作者主观总结，不代表绝对，不定期更新。
No.1
当题目中具有限制性的条件时，如B题，可以在最短路的基础上直接内嵌条件，典型代表是Dijkstra，直接在更新处加条件。
如果题目中限制性的条件具有传递性，如B题，可以在维护单源最短路的同时维护每一个点的限制条件，按照题目给定的要求更新条件，相当于在限制意义下求最短路。
No.2
当题目中没有直接给出图，需要自己建图时，多半建图会是题目难点，以C题为例，C题给出的是边，需要自己建点，建点可以利用并查集查重。
No.3
当题目中具有限制条件且限制是最值性问题时，可以利用二分答案进行降维，如D题与F题。
No.4
当题目中除了传统意义下的边之外还有额外的移动手段，例如G题，如果在最短路中暴力查找，一般是超时的；需要根据题目的一些特殊性质把暴力查找转化为一些特殊的边或点，例如G题中对于每一个深度都具有两个转节点，分别用来管理入边与出边，需要经过大量的转化。
No.5
题目中给出的边往往是可以映射成点的，例如H题，把边看作点，整个题目难度直接降维，顺带提一句，C题其实也可以把边看成点，对于每两条边缩成一条边，边权为之前两边权之和，可以发现最小环的大小正好被扩大两倍。（我好像是第一个想出来这种做法，但没有写）。
No.6
一个简单的性质，设最短路上一点u，最短路起点s与t，那么s到u的距离加上u到t的距离等于最短路长度，例如J题，搭配Floyd使用更佳。
No.7
求最短路的条数，可以按照最短路的更新镜像更新，最短路怎么更新最短路的条数就怎么更新，可以看成是DP的计数问题。例题：K题。
No.8
当图中的边权仅为0或1时，可以考虑使用BFS搜最短路，边权为1的正常入队，边权为0的提高优先级，从队头入队，这样可以保证队列中的元素一定单调，相较于单源最短路(Dijkstra)有一个log级别的优化。
No.9
当图中的边不容易直接处理时，可以试试将边拆分，例如I题。
No.10
对于单源最短路，如果将所有在最短路上的边取出重新建图，那么这个图一定是DAG，但有一个前提，就是边权为正数。如L题，将图建出后，因为是DAG，所以自然想到跑拓扑排序。
No.11
有时候题目并不一定直接求最短路，但我们可以利用最短路更新的信息来做些其他事，比如P题，利用最短路信息做dfs的剪枝，比较新颖。
No.12
随机化策略本就不太常规，除非题目给出特别的性质，比如大于一半这类的字眼，而且一般随机化的题目是会保证一定正确概率。但有些题目没有保证概率，例如R题，显然跑完是直接爆炸的时间复杂度，但我们考虑把点通过二进制按位分成两个集合，因为题目保证起点与终点不同，巧妙利用二进制进行分组，既保证了答案正确，还节省了很大一部分无效计算，是一种 全新的套路。