动态规划初步

Update 2019.8.23

  • 又回来刷题了。。。。

  • 最近发现小绿本(《算法竞赛入门经典——习题与解答》)上的题值得一做,题解都写得很清真,不会像某谷上的题解,有一些奇技淫巧,不看 $Code$ 的情况下一般都可以打出来,提高自己的代码实现能力。
  • 然后我就先从动态规划开始吧 $qwq$ ~~

2019.8.19 集训笔记

讲数论,$tql$ !

A* 启发式搜索

新的算法当然要新开一片博文来水 ^ _ ^,我竟然这么久了才学这么垃圾的算法。。。。。


图论的各种奇技淫巧

就是想复习一下图论…..

平衡树

  • 我自己的复习就开始从平衡树开始吧$qwq$
  • 这是我最早咕的一个知识点,现在来看,我那时菜得竟然连$Treap$都看不懂,$emming$
  • 最近在刷洛谷试炼场的时候,做到了P2330这道题,一看到有个生成树的条件是要让最长的边最短,感觉很熟悉,记得最小生成树就一定满足这一性质,但是还是不会证。
  • 于是我就百度了一下$QAQ$

SPFA算法深度探究

SPFA??它已经死了,完结撒花~~

图论里面有一个致命的东西,那就是负权边,现在我会的算法中能解决负边的只有$O(n^3)$的$Floyd$……遇到负权边我们还是要向死了的SPFA伸手


↑↑正文分割线

  • SPFA说的牛逼一点就是$(Shortest$ $Path$ $Faster$ $Algorithm)$,说的谦虚(全球化)一点就是队列优化的$Bellman-Ford$算法。那么这个$Bellman-Ford$又是什么东西呢??

$Bellman-Ford$算法

  • 我在寒假集训Day1的笔记里曾提到这个东西,松弛:$dis[v]=\min⁡(dis[v],dis[u]+dis(u,v))$

    • 核心代码:
    1
    2
    3
    4
    for (int k=1;k<=n-1;k++)//n是顶点的数量
    for (itn i=1;i<=m;i++)//m是边的数量
    if (dis[v[i]]>dis[u[i]]+w[i])//u[i]和v[i]是边的两个顶点
    dis[v[i]]=dis[u[i]]+w[i];//w[i]是边的费用
    • 分析:首先,为什么要进行$n-1$次呢??因为在$n$个顶点的图中,任意两点的最短路最多包含$n-1$条边。这样算下来,时间复杂度是$O(nm)$,当然还可以优化(不是SPFA),可以发现我们常常在$n-1$次循环以前就完成了所有松弛,如果发现某次松弛没有发生变化,即可提前跳出循环。
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×