NOIP算法总结
临时抱佛脚
阅读全文DP总结2
上一篇简单的介绍了DP的实质
这一篇介绍DP的应用啥的
阅读全文DP总结
以前一直想写一个总结,但因为太蒟蒻了(现在也是
最近对DP有了一些见解。。。就写一下吧。。。
阅读全文各种树结构之一 二叉查找树
好久没动数据结构了,今天就来一发。
之后的几篇都会介绍树形结构。。。what a flag
在竞赛中对拍程序的书写
对拍,就是用一个随机数生成程序不停地生成数据,把数据放到一个暴力/标程和比较快的不知道是不是正解的程序中,比较输出。来测试近似正解的正确性。
阅读全文线段树学习笔记
线段树概述
线段树,类似区间树,它在各个节点保存一条线段(数组中的一段子数组),主要用于高效解决连续区间的动态查询问题,由于二叉结构的特性,它基本能保持每个操作的复杂度为O(logn)。
线段树的每个节点表示一个区间,子节点则分别表示父节点的左右半区间,例如父亲的区间是[a,b],那么(c=(a+b)/2)左儿子的区间是[a,c],右儿子的区间是[c+1,b]。
阅读全文图论知识综合
图论的知识终于坑完了。。。要疯狂刷题了。。。
阅读全文图的遍历
本文介绍的算导上的图的遍历。。。很基础
阅读全文图的储存
最基本的图论。。。但是也不能松懈啊
有邻接矩阵,邻接链表。。。
阅读全文图的最大流算法
最近坑了最大流。。。疯狂的图论
最大流真是神奇的算法。。。震惊了我好几次
阅读全文Prim算法与Dijsktra算法的异同
写完最小生成树与最短路,大脑一片混乱。。。尤其是prim与dijsktra。。。理了一晚上才出来。。。
阅读全文图的最短路径算法
接着坑图论。。。
好久以前就想总结一下了。。。各种最短路233
floyed、dijkstra、bellman、spfa。。。
阅读全文最小生成树的相关算法
学完最小生成树就来学习下它的相关算法吧。。。
在最小生成树的实际应用中我们常常会遇到这一类问题,给你一张无向带权连通图和两个节点u,v让你求u,v之间的一条路径使得u->v路径上最大的边权最小值。这一类问题我们称之为最小瓶颈路问题。
阅读全文最小生成树笔记
无聊了再坑一坑图论吧。。。啥都搞不好。。。
给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,这叫最小生成树。。。
有两种著名的算法。。。prim,kruskal。。。
prim的效率取决于优先队列的实现与图的存储方式,这里记顶点数v,边数e 邻接矩阵:O(v2)、邻接表:O(elog2v),若用斐波那契堆作为优先队列则效率为O(e+vlog2v)
kruskal的效率取决于并查集的实现,若用按秩合并与路径压缩效率为O(elog2e)
阅读全文