• 学习笔记

    欧拉回路学习笔记

    下面的内容主要是是搬运的陈通的集训队论文,可能会有点私货和代码(大雾)。 论文链接 基本概念 定义1.1:图 $G$ 中经过每一条边恰一次的回路称为欧拉回路,经过每条边恰一次的路径称为欧拉路径。 定义1.2:存在欧拉回路…

  • 题解

    【USACO5.3】校园网Network of Schools

    题目描述 一些学校连入一个电脑网络。那些学校已订立了协议:每个学校都会给其它的一些学校分发软件(称作“接受学校”)。注意即使 B 在 A 学校的分发列表中, A 也不一定在 B 学校的列表中。 你要写一个程序计算,根据协…

  • 题解

    【HNOI2009】最小环

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

  • 学习笔记

    Dijsktra算法

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

  • 学习笔记

    【模板】SPFA算法

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