• 题解

    【HNOI2009】最小环

    题目链接 【HNOI2009】最小环 思路 题目要求输出边权平均值最小的环的平均值,再看一眼数据范围,不难联想到我们可以二分答案。剩下的就是如何去check我们的答案。我们让所有边减去一个我们二分平均值,如果存在负环,说…

  • 学习笔记

    Dijsktra算法

    Dijkstra算法是一种用于求最短路径的算法,用于求一个节点到其他所有节点的最短路径。与其他的最短路径算法一样,都采用松弛操作,并且运用了贪心的思想。适用于处理不存在负边权的稀疏图,算法的时间复杂度为 $O(N^2)$…

  • 学习笔记

    【模板】SPFA算法

    SPFA算法是Bellman-Ford(蛤?你说你不知道Bellman-Ford算法?)算法的队列实现方法,采取动态逼近的方式来求得单源最短路,时间复杂度为O(ek)e为边数,k是所有点进队的平均次数。适用于不存在负权回…