图论的各种奇技淫巧

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

CSP2019.3考试记录

Update 2019.8.10

更新了挂掉的链接 qwq,然后来耍耍存在感 QAQ

  • 最近被老师拉去考了一个$CSP$,什么$CCF$职业认证考试…..
  • 考点在$S$大,用那里的电脑连接$CCF$的华为云服务器,在那里做题,真是太傻逼了
  • 代码要钱,我太穷了,所以没有任何$Code$。

2019.5.26高中部集训

  • 今天考试

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$次循环以前就完成了所有松弛,如果发现某次松弛没有发生变化,即可提前跳出循环。

题面

  • 安利一发Blog,不点进来看下吗??
  • 这道题可以说很很很很恶心了ヽ(#`Д´)ノ,恶心的是建图。本来想抄的题解的,但是题解里面$Floyd$的题解不是特别详细,关键是不符合我的码风!!所以还是自己敲了个​(很丑的)$Floyd$。难度应该是绿题吧,我觉得,但是蓝题也不是特别夸张(逃
  • 该题还有一个难点就是找一个城市中的第4个点,用勾股定理判断直角三角形的直角,从而判断第4个点。(题目中说了4个飞机场围成矩形哦~~)
  • 最后说一个做题技巧:碰到繁琐的题目要多封装韩硕,不然会把自己弄晕的,也不好$Debug$~~
  • Code:很多细节在代码中哦~

高中部寒假集训Day1

Day1:

emming,高中部集训在春节前要上5天,春节后上2天(如果我没记错的话QAQ)

学校的电脑系统重装了一遍,把万恶的冰点还原(^-^)和教师监控系统(但是我怎么接老师课件啊QAQ)刷掉了,嘿嘿嘿。

以上是废话。


今天课程表:

Your browser is out-of-date!

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

×