开始录制好我们看一下啊
这里的话是两个红苹果三个绿苹果
如果说一次拿的话
同学们我们思考一下
我们是不是就需要把这三个
绿苹果打包放在这一个框里面
对不对对吧
然后如果说是分两组的话
同学们其实我们可以看啊
我们这三个绿苹果可以放在哪里呢
是不是可以放在这个空里面
可以放在这个空里面
也就是说如果是两个红苹果的话
我们是不是有
三个空可以放
是不是可以放三个框
嗯对不对
这个能听懂吗
那我们是不是就可以任选
任选其中的一个空2
也叫C31
任选一个空2
能理解吧
如果说是有x的苹果呢
有多少个空呢
有x的红苹果有多少个空呢
x加一哎是不是c x加一的空2
如果说我们要分成
我们要从这里边任选一个空
放绿苹果的话
我们是不是就是
CX加一如果说我们要在里边
挑两个空放苹果的话
是CX加2
呃加一二
如果说i空的话我们是不是就是哎呀
那是不是就是I4拿走啊
能理解吧
然后接下来的话就是我们这个苹果
绿色苹果是不是又要分成
你比如说三个苹果
三个三个绿苹果
我们把它分成一组有几种分法呢
一个如果要把它分成两组呢
三种三种怎么分
两个数一二两个3啊
是不是因为都是一样的苹果对吧
是不是一个两个
两个一个两个一个
对吧如果说是五个苹果分成两组呢
分成三组呢
这叫什么
是不是叫隔板法
是不是
是不是隔板法
相当于是你是不是在这里面几个框
是不是四个框
任选两个框是不是可以分成三份
所以假如说你现在有这个绿苹果
你有多少个框呢
c
减一个框你要分成
分成iPhone
那你需要隔几个板呢
CG减1 II减一个板对不对
对是不是CG减1I减一啊
然后再乘以我们的c
2加1I
这就是我们的答案
对不对是不是先给我们的
红苹果
他之间的所有的空我们都可以放
绿苹果
我们要分几组我们就放上几个
是不是要挑出几个空来
那有多少空呢
一个空两个空3个空4个空5个空
所以说CR加一个空
因为要分成i组吗
我们就挑出i个位置
对吧然后
这里的话就是
我们要把一个把这么多苹果呢
分成几份
隔板法所以的话就是g减一个
j点一个空
加上i点一个隔板
是不是这就是我们的答案
这是第一题
简单一说哈我我们就不详细讲哈
你你究竟怎么做你自个去做啊
我只是告诉你这个解题思路
第二题的话叫做电梯
电梯的话是一道非常好的动态规划题
同学们应该学过动态规划吧
对吧
嗯应该是学过啊我记得好像讲过
那这个其实是一个背包类型的问题
啊背包类型的问题
非常非常好啊这个
这个题其实也不能叫非常好啊
反正对于你们肯定是非常合适的
我觉得这道题确实不错啊出
的还是有水平的
那么
电梯的话呢
假如说这是哎读没读题啊
带你们读下题吧
你比如说假如说我们一共有n层楼
一层楼你当前在a位置
b位置
n层楼
你在a位置的话你要走
你要到达x点
那有一个要求就a减x小于
a减b
有这样一个要求
那么假如说
哎这是这是我们的要求
这是题目的要求哈
那你看啊同学们
那么a减b是不是就是这一块距离啊
那所以所以
我们可以走的范围其实就是这一块
就是我可以从这些位置移动到a点去
哎呦马上到于小宁马上到啊
能能理解吧
就是说
我我这一块的位置是可以移动上去的
到就是我从a点可以移动到这些点去
啊这是提议
这是提议哈
那么怎么去做呢
怎么去做呢
哎非常简单
我们可以考虑
因为题目要问我们就是摁K4电梯啊
我们先不管K4电梯
假如说你当前站在a位置上
我们是不是就可以转移啊
你是不是可以转移到哪些位置啊
是不是可以转移到某些位置去啊
那这些位置我们是不是可以求啊
这些位置的话是不是就是
假如说这是l
指啊我是不是可以从l到r
这些位置我都可以移动啊
除了a本身
但a是不能转移的是吧
哦原来已经到了
L2是都是可以转移的
但是a这个位置是不能转移
因为你不能按按一下
楼层按到自个本身去嘛对吧
所以这个地方要要注意
那么
我们其实就可以做一个动态转移方程
比如说就是f
啊我们可以用刷表法去做
假如说你当前是a位置
那么所有的f l加等于a
加等于f a
一直到f r
加等于f a
就是你在a位置有多少种方案
那你就可以利用刷表法的方式呢去
移动到l位置
加就是经过一步你到达l位置
还有r位置之间的某一个位置
都都可以
那么这样做的话
我们其实是一个三重循环
最外层的话是KK重循环
然后接下来的话是我们的当前位置a
再一个的话就是l到2
就也就三三种循环
而我们的数据范围的话好像是5,000
5,000的话
毫无疑问
我们这个三种循环的方法是要超时的
但是我已经帮你们测了能得60分啊
能得60分
所以呢我们就需要对他进行优化
那我们刚刚是采用的刷标法去做
我们还可以用
啊对填标法去做也是可以的啊
填标法也就是说我到达当前位置
我是从哪些位置转移过来的
我从哪个位置可以到我当前这个位置
我们也可以求
假如说我目标到达j位置
我是可以求出l r位置的
那么我们可以发现
我们其实就是把这一段的区间的值
加到f j上去
f g加等于f l
加等于f l加音
其实就是加等于c个嘛
比如说我们用c变量c等于LC等于RFC
但是这里有一个要排除
就是你不能从f
g转移过来
所以说你是虽然从这里到这里
但是没有c还不能等于g
这个位置转移过来
对不对那么我们可以发现
我们是不是从上一维里面
挑一块区间
转移过来啊
那块这块区间是不是就是一个什么
是不是把这里面每一个值加加过来
相当于把这一段的区间
听课
把什么加过来啊同学们
是不是把区间盒加过来
所以我们是不是可以
预处理一下我们的区间盒
然后直接加等于S2减掉SL减一
再减掉SG啊
能理解吧
那这样的话我们就给他做了一个降维
降维的话就变成了欧恩方做法
然后外层循环的是k
内层循环的话是j
然后这
然后我们另外
还要顺便维护一下我们的前缀
和s
就可以了这道题还是非常不错的啊
嗯照题是我昨天最后一个做出来
呃因为他考到12点
我中午回家的时候就11点多了
我做了两个
呃对他他昨天
晚上才又开放了啊晚上才又开放了啊
对然后是
呃打球这个题
打球这个题的话其实呢
呃相对比较简单是一个前轮和加2分
我不想讲啊这个题我们不讲了
因为这个
这个题没有说是什么
我们要考察哪一种算法啊
就是一个模拟模拟题哈所以不讲了
摔柄这个题的话是一道图论题
啊图论题的话
你因为你们图论现
在属于是你们的弱项
也没读题是吧
都没读题
你你们图论题肯定是比较弱的
所以咱们就先
这道题是我第一个做出来的
我倒着做的啊倒着做的啊
然后然后
那那这样的话咱们今天就学新知识吧
比如说讲两个题
那两个题我认为是你们能做的
一个是排列组合
我们讲过排列组合对吧
再一个是呃背包的变形
只是加了一个优化前缀和优化
这是一种很常用的优化方式
就是在这个动态规划当中
非常常见的一种优化方式
因为我们还没有讲
这个动态规划的优化
所以呢这道题的话
可能对于你来说你能得60分就行
比如说做一个o n三次方
这个转移方程出来也行
然后尝试着去把它进行一个优化
就可以了啊
然后我们今天的话
来学习下我们的这点路
嗯这样说的话方法有很多啊
我们重要的讲啊
就是今天的话我们讲这个迪杰斯特拉
啊基本上
这节课也就只能讲这个迪杰斯特拉
如果有时间的话
我们讲一下这个
跟迪亚斯拉非常相似的一个普利
姆算法但是求最最小生成数
我们上节课已经
啊就是教了一种求罪要生生术的方法
同学们还记得吗
对
对开心啊
我们是
用一个编辑数组存放我们所有的编
对吧存放我们所有的边
然后由短到长的话
去将它加入到我们的集合当中去
如果说产生了环的话这条边就不加
我们是要不停的判断是否构成环
只要构成环我们这条边
呢就不加因为竖的话是没有环的
对吧
啊所以呢只要构成构成环我们就不加
最终的话我们是n个点
我们要加上n减一条边
我们就可以构构造成一棵最小生成树
啊采用这个贪心的策略啊
这个方法的话应该是比较简单
那么今天的话
我们来看一下我们的普利姆啊
DJ斯特拉算法
那么DJ斯特拉算法
上节课的最后
我们也已经讲了一点他的
思路啊就是他的算法的原理
把DJ斯特拉算好
哎DJ斯特拉呢是DJ拉斯特拉发发现的
好像是一九五几年就发现了
一九五几年我们还在还在闹革命呢
涂改叫什么
算了不能说了
再说上传上去
又又又看不了了又看不了了哈哈哈
啊对对吧
你看他们就开始搞这种犯法了对吧
所以
我们距离他们的距离还是很遥远的
你看我们现在还在学他们的东西
那么迪亚斯特拉的话球最短路
什么叫做最短路呢
我们这个呢叫做球单元最短路啊
一些概念
概念性的东西我们以前都讲了啊
那么这里有一个叫做单元
什么叫做单元呢
从某一个圆点出发
比如说我们指定圆点从s点出发
到其他点的最短路径
叫做单元最短路
能理解吧
从某个点出发到其他点如果说是我们
呃比如说从所有的点到其他所有的点
到最短路的话
那迪迪斯特拉呢就相对比较慢了
但不是说解决不了
就像是我们上个月约赛的最后一题
他就让我们求一个多元最短路
求一个多元对短路
但是他告诉我们我们的呃k值非常小
我们就可以暴力一下去用这个
呃DS大拉去做一下
也是可以也是可行的啊
那么呃其他的我们不多说
我们呃明确就行了
我们求大家最短路径
必须要掌握的就是DJ斯特拉算法
然后我们来讲一下它的原理
比如说我们现在这里有个图
随便画一画
假如说是有像图
然后我们要去
求某个点到其他点的对短路线
那么我们上节课已经讲过了
我们是要把
我们所有点的构造成两个点级
一个是s点级一个是t点级
s点击表示的是
哎对已经求得已经求得对暖路的
那t点击的话表示还是未求得
没有求得的
所有的点什么意思呢
你比如说我们1234
在t里面
就表示现在这4个点的最短路
我们都没有求得的
对吧
然后如果说我们现在求得了一的
我们就要把一从这个集合当中
拿到另外一个集合当中去
就表示我一点的对短路已经知道了
而其余的点的对短路我们就不知道
然后当我们把所有的n个点都求得了
也就是说把所有的点
都从t集合拿到s集合当中去的时候
我们所有的点的最短路径
也就都求得了
能听懂吧
啊这个比较简单是吧
那么我们求最短路的方法是
又是什么呢
我们这里呢有一个
啊过程我们来看一下
这个比较重要啊
这个其实呢就是你以后
你去记代码你是很难记住的
就是说这个代码你要去背的话
当然你肯定要背
但是如果说你过段时间忘了
也没有关系我们只要理解这个过程
你就一定能再写出来
如果说你这个过程不理解
你光在想我当时是怎么写的
那毫无疑问
你这个代码肯定是有问题的
我估计你也会写错
所以这个过程
比这个背把代码背过呢
应该说是更重要啊
我们来看一下
首先将节点分成两个集合
已知最短路的点集
也就已知点集s集合和未知点集
t集合一开始所有的点都是t集合
也就是说
最开始我们所有的点的最短路
我们都不知道吧
对吧但是我们呃知道一点
就是我们要从s点出发的话
那么diss就等于0对吧
就表示从我出发到我自己本身的话
最短路就是0
那么到其他点应是未知的
我们就设置为正无穷
对吧这是初始状态
也就是说
最开始的状态其实就是这样一种状态
两个集合
一个是s集合
一个是t集合
最开始的话我们所有的点呢
都在我们的t集合里面
那么我们如何去表示这个点
在哪个集合当中呢
同学们非常简单
因为我们只有两个集合
我们就可以用一个with速度做标记
用VSI等于一表示i在s集合当中
如果说VISI等于0的话
就表示它在t几何当中
能理解吧
非常简单
那么另外的话我们还需要有一个DISD
DIS的话表示的是dis
i表示的是
圆点因为我们是单元最短路
我们要从s出发到达i点的最短路径
是多少对不对
所以我们就要需要去维护这样
两个速度
一个呢就是他在哪个集合当中
另外一个的话
就是他到他的最短路径是多少
最开始的状态呢就是这样的
也就是说我们
可以思考一下
我们先把这个过程描述一下
然后再去写这个代码哈
最开始的时候
出入状态的话就是全部设置为Infinity
然后呢
我们
进行下载操作
重复执行下载操作
这这个地方的话就是
所有的点都是以分类型
只有d d 40 s等于0哈
第一步呢就是从
这个其实比较关键就是哎
我们去找所有的点
到这个集合里面的最短路是多少
我们来抽象了思考一下
假如说这是已经知道了这些点
这是位置这些点
然后这些点是不是到这个集合里面
是会有一些边存在
两个集合之间是不是有些边存在
对吧两个集合之间有一些边存在
那么这些边
里面是不是就有一个最短的那个边
那么我们思考一下
我们这里有一个前提哈
就是DJ斯特拉球对短路径要求
所有的边是非负边权
没有负边
有环是可以的啊啊
但是不能有负啊
不能有负要非负别权啊
不能说有负数啊
没有副边这两个不是不是
如果说你有副环
你你你会在某个环里绕圈
圈啊对能能背负边球
这两个不就是没有环
他是可以有花的
就是我们是可以有花的
你比如说这是一个
我们求这个点到这个点对上了
我们不是可以有花吗
你你最终这个
你不可能说是经过n个点回到自身
更短就是了
啊
最短求出来的最短路是没有环的啊
你不可能说出现有一个环
因为因为我要有一个环的话
我们可以简单的用反正法去证明对吧
啊对吧
那在这里的话就是我们有一个前提
就是我们的所有的边圈的话
都是非负啊
如果有负边圈的话
他就有可能出现负环
出现负环的话他就有可能在这绕圈
对吧所以呢我们必须加一个前提
前提这个你也要
就是做题的时候要特别小心啊
如果说有副边权的话
我们用另外一个方法SPFA去做啊
这这个就是后话了啊这个以后再说啊
那么这里面所有的边的话都会有一条
一定会有存在一条最短的边
那么我们会思考我们有没有一种方法
我从这里面的点到达这里的点
然后再从这个点到这个点更短呢
有没有可能呢
有可能吗
这是最短这个已经是最短
我们有没有可能通过这样的一条路
到这个点更短呢
不可能
这也是为什么我们要确保是恢复的
对吧啊
当然了这个其实也是
我们主要还是要避免复活啊
主要还是要避免复活啊
然后那么这条路的话
不可能再存在另外一条路比他更短了
所以那这一个点是不是就是下
一个最短路啊
就是就是我们
到这个点的路径是不是就最短路了
我们是不是就求得了
到这个点的最短路
因为你不可能再走其他路到达这个点
最短吧
你不可能再有其他路所以这就是最短
所以呢我们就要把这个点
拿到这个集合里面去
能理解吧
这是第一步
也就是说我们先找到最短路1
啊第二步拿过去
拿拿到s里面去
拿到s里面去
其实非常简单就是VIS
等于一就行了对吧
假如说我们找到这个点是u的话
我们是不是就可以把优点
放到我们的s
集合当中去啊
听课啊
那第三步的话叫做松弛操作啊
松弛操作就是我们现在
新一个新的点到了这个集合
那这个点是不是还连了一些边
到这这里的一些点啊
对不对那么我们就可以去更新一下
所有这里面的点
到这里面的点的最短路径
因为你现在有个新的点进来了
原先的话是这样一个字
如果你有新的点是不是会
他有可能会给你增加一些新的点
对吧
所以呢我们要去进行一个松弛操作
松弛操作的话
其实就是更更新你这个对短路
更新他不叫对短路
就是可能的对短路啊
松弛操作
总共就这三步
我们的
这个上面也写了对吧
从d集合当中选取一个最短路
长度最小的节点
移动到s集合当中
你能不能啊
你能不能保持安静
第一个第一步先找到最短路
第二步移动到s集合当
中去第三步的话对它进行松弛操作
要新加入的点
有可能会更新我们的
s到t集合的最短路对吧
那么我们就要对他进行一个松弛操作
松弛操作完之后呢
我们是不是就完成了一次操作
完成一次操作哎
我们的目标的话就是要
把所有的n个点
全部从t集合当中拿到s集合当中去
也就是说我们要执行
n次这样的操作就可以了
这是我们的算法的原理和思路过程
呃啥玩意
我们不是有SV 0吗
那SV 0最短的不就是0吗
然后我也就说
第一个拿进去的其实就是圆点
对不对第一个拿进去的就是圆点
接下来
我们拿过去以后我们是不是要更新啊
就是跟s相邻的点是哪些
我们是不是就可以去更新一下我们的
face输入啊
只更新相邻的吗
只更新相邻的啊
这这松弛操作你如果所有的都更新
那你的复杂度就很很高了
对吧所有的都更新复杂度就会很高
好那同学们我们一块来写下
我们这里有有一个立体啊我们找一下
啊章节7我们中间跳了几个章节啊
呃自个去那个把BFS山DFS补上啊
其他的我们后面肯定还会讲
有机会再说
啊我们把最先把重点的先讲一下
因为这个有可能会在
暑假的时候呢没有时间讲啊
没有时间讲
好我们去做一下这道题看一下
呃另外呢老师呢最近呢也
用了一个新软件
啊对
呃一块都跟着我们
一块打一下啊不准在那那混啊
我发现有很多同学在那混
就就就是光带着耳朵来听一听
绝对不会打的
我们有多种方式哈
我们这个题的话
我们采用相对难一点的
列式前向心
作为存读方式
那这个对对那个谁就不太友好了
对那个袁敬轩就不太友好了
袁敬轩旷课两次
啊对吧旷课两次不会不会存图啊
你以后不能旷课
什么乱七八糟比比赛不要参加了
那么我们呢就是嗯呃做一下n m
他还有个s是吧
题目读一下
这个题其实就是路虎上的一道题
33371题
好像是3371啊
给你一个有效图
呃给你N m s啊分别表示点的个数
编的个数以及出发点的编号
接下来给你m条边
偶像边
长度1W
然后我们目标的话就是输出
s点到其他点的最短路径
因为是有向图吗
也有可能不呃不联通
所以我们还是有可能到某个点到不了
如果说不能到达某个点的话我们呢
就输出2的31方减一
没有问题吧
题目非常简单就给你个图
求这个比如说一点
求一点到其他点的最短路径啊
啊求一点求s点到其他点的最短时间
那么第一步的话就是存图啊
那么我们在这里定一个Infinity
infinite的话
它告诉我们是二三十一方减一
我不知道在座各位有没有背过的
我反正是没背过
二的三十一次方
哎就是我们的最大值是吧
啊最大值
这个题其实也要考虑一下啊
看一下我们的数据范围
数据范围的话呢是
他们这里确保啊
我们的和加起来是小于2的31方的
看到没
这个地方其实比较关键
如果说我们的和加起来
比2的31同方还要大
那么我们是不是就有可能存在一条边
一个点的对断路径是大于他的
我们我们反而去
反而我们的初始值更小
他不是正无穷了
所以这个地方要特别注意啊
就是c个码w
要确保他是小样的31平方
同学们可以思考一下这样一种状态啊
假如说这是s点这个对应的点是x点
s点到x点的
点的这个路径的呃全值呢
比我们的Infinity还要大
也就我们的正解
比我们的Infinity还要大
然后你初始化的时候
给它初始化为Infinity
那你是不是对他进行无
无法对他进行松弛操作了
所以这里他也告诉我们了哈
就是这个要注意就是
c个么w的话是小于二三十一方的
所以就意味着所有的边
等和都小于这个点
都都都是小于你飞进去的
比较安全啊比较安全
啊继续
就是你用哪个软件都无所谓哈老师呢
只是
其实用这个软件上课是不方便的因为
因为他那个
数据太小你可能看不清楚啊
但是做题确实比较方便啊就是他会
他会自动的帮你把那个题目的数据呢
呃读读进来啊
然后测的时候也相对比较方便啊
好然后我们呢
在这里用我们的练习前小星去村边
朋友们还记得吗
哎对了忘了检查你们的博客了
这里呢因为他是有编权的对吧
这里是有鞭权的是吧
还记得怎么写吗
忘了是吧同学们
是不是忘了同学们
你说你们学
同学们
我昨天上午
陪床办理出院
下午上课晚上上课
我昨天都把那个比赛题打完了
还做了
还做了好几道那个动态规划的题
顶多了10道比较有难度的题
请问在座的各位你们呢
决定圈小圆呢
小圆做了几个题
上课去了
一个都没做
就你就说一个都没做就行了
还上课去了
对不对小张呢
啊啊5道左右
5道左右
哎呦
嗯迟到迟到哎还行
小张还行啊小赵呢
啊对我我我做了几道a加b
我每周每天做3次a加b哈哈
啊对啊每天做3次a加b
对吧你怎么知道我的习惯
哎对找找自信吗找自信
最基础的存图操作啊一定要掌握啊
因为它是有像图对吧
所以我们只添加一次边就可以了
这个地方要特别小心啊
刘浩林
刘浩林去呃这个今年2月份考CSPG
第三题给了一棵树
给了一棵树
然后他就告诉你负
这个两个节点相就是相邻
然后他就只操作了只把他当有项
边就出
那很明显他有可能给你一个边是一二
也有可能给你给你边是2一
你哪知道附近人是谁呢
对不对所以你一定要明确
这个地方究竟是有像图还是无像图
有像图的话我们就只加一条边
如果是无像图的话我们要把它
看到是两条有像边去处理
对吧
哎对不对
然后采用我们的DJ斯特拉然后最终呢
输出我们的路径就可以了
比较简单哈
思路也比较简单
没问题吧
好那么我们来写一下我们的DJ斯特拉
那我们说了我们要维护两个数组对吧
表示
i点是否在s集合中对不对
d数组吧
最短路径
注意哈我们呃
只有最终你把它加到s当中去以后
我们这个d才是最短路径啊
否则的话
它只是过程当中的可能的最短路径啊
也就是说我们的DIS
就说我们这个d啊
是在不停的更新
更新完了以后
最终的状态才是最短路径啊
另外呢
其实我们还可以去构造一个p数Pro
这个速度呢跟球队两路无关
但是我们顺便一块讲了啊
就是假如说我想问你
s到x这这这条这个
s到x最短路径的路径是怎样的
也就说我不
我不仅仅要问你的最短路的值是多少
我还要问你经过了哪些点到达了x点
那么我们就做一个Pre
就表示我的上一个点
我是从哪个点来的对吧
啊从哪个点过来
那这样的话
我们到每个点都去维护出来的话
我是不是思考一下哎
我从哪个点来的
他从哪个点来的
我们是不是就把这条路径找到了
能理解吗同学们
好第一步根据我们的
根据我们的算法过程啊
第一步
初始化所有的最
难录DIS也就是我们的d
对吧
如果说我们是要求boss
比利时特拉的话
在这要小心
要更新
啊vs
因为我们只求一次
所以我们就不更新了
这里要注意啊同学对不对
如果你要求多次的话
我们是不是要更新一下
对吧哎
若要多次的话
我们是这个Pro也要更新一下
我们在这不不不多赘述了啊
找把执行n次
执行n次
把点从t集合移动到s集合的过程
对啊是不是直接N3
我们要找n个点的最短路嘛
对不对
找n个点的最短路
找那个点的最短路的话
我们是不是分三步走啊
哎我们的
这里是不是有三步啊
第一步找到最短路的节点
第二步移动到s集合当中
第三步松弛对吧
哎一步第一步
找到最短路的结
2
移动到s
比如说我们找到最短路减点u吧
我们用u表示好吧
把u哎有人敲门吗
哎哦
对对对我忘了
你们忘了
时间时间得看你了啊
你看这个花那个
那个的话应该还行应该是
去哪
对啊
你去屋里找个凳子
然后挨着旅行
你自个以后带电脑
啊把u移动到s集合吗
因为我们是不是找到最短路的节点
u嘛
第三步第三步是什么呢
进行对u点进行松弛操作啊
就是对u的
跟u相
邻的节点进行松弛操作
其实呢我们也可以这样理解就是跟u
相邻的在
t集合中
跟u相邻的经典语音操作
对吧
哎应该能理解是吧
那第一步找到
最短路点点我们用朴素的做法的话
这个学过吗
那个私家语啊DJ斯特拉
好像忘了
天天不做题
那肯定忘啊哎找到you
其实就是求一堆数里的最小值嘛对吧
非常简单
对吧
这个应该是非常简单的啊应该是
很容易理解啊
就是先设一个最大值
然后去找这里面最小值的是第几
找到了以后呢就找到了我们这个点
啊你用啊你要用我的电脑吗
密码我得我得跟你说我不能告诉你
我还密码
什么密码
对吧我再给你个10块钱的啊
密码是一
算了你不用写了你听吧
你是一啊现在
密封卡密码56
哎密码错了
按着密码不破了用电脑就PK原带齐了
哦对算了你还是别用我电脑
哈哈
我刚刚听说他最近学战
然后直接学战和电脑
他就忘了
战
战和电脑
你不用电脑
你不需要电脑你跟他看一个就行
你你用大脑大脑写代码就可以了
大脑写代码
因为我最近正在出比赛题
我不能让你们看到
啊哪个比赛啊
蓝图杯啊
据说蓝图杯这一次的比赛
是作为选拔赛啊
就会选选一个夏令营出来
啊然后参加这个高新区的夏令营
这个老师教我
你教我聘请你去当老师好不好
多少天 10天吧可能是10天啊
免费又是免费
又是免费
7月底吧可能是7月底就跟去年差不多
去年不也7月底吗
去年
但是是高新区的
在座各位有几个是高新区的呢
坏了没有高新区的我们这班里
我靠
我们这班里只有傅家玉是高新区的吗
哦王一正
没有其他人高新区的
哇那我们去不就行了吗
还是哪的
太悲哀了
没事我们
我们别的班有高新区的孩子
哎呀看来我太失败了
我高新区的孩子去了
然后这个是不是又找到优点了
找到优点了对吧
然后VSU等于一
是不是就移动到s集合当中了
啊移动到s集合当中
那接下来对对
是不是要进行一个松弛操作
我们刚刚这说了是吧
是不是所有的跟优相邻的点
在t集合当中的点的
这个路径值
我们是是不是要进行一个松弛啊
更新啊比如说
如果说我到达通过优点到达某个点
更短的话
我是不是叫松弛操作
松弛操作的话其实就是非常简单哈
我原先
比如说v点
这是DV
那么现在假如说我通过优点
再到达v点
更短
对不对原先是不是这样一条路啊
其实这个s的话
你你你应该是理解为是一个集合啊
那我通过乱七八糟的路径
到达危点是DV
而如果说我经过优点转车
再走一点的话
更近你比如说你直接去美国
海关就把你弄弄住了
你要你若走洪图拉斯
然后步行走到什么墨西哥
对吧说不定你还能进进入美国是吧
哎就是这条路更短的话
那么我们就对他进行更新
我们就走这条路到达危点
也就是说低
于低微
等于d u
加w这条边的值是w的话对不对
如果这条路更短的话我们就更新一下
做一个松弛操作
那么FO循环
练习天上星吗
加HDV
大于DU加w
当然了我们这里最好加一个心理条件
因为是找的是在t集合当中的
但是不加也没关系啊
就是正说的话是不加也没关系
加不加都行
因为我们一定确保到s
集合当中的最短路
一定是最短的
所以你一定无法更新
所以我们在这个地方加不加这个微
呃VSV000都是无所谓的
这个就是加不加都行啊
但是为了就是跟我们
这个过程符合起来
我们我们就是更
我希望我们的思路更清晰
我们是不是要更新t级合理的点了
对不对啊
就是t级合理的点
那就是vs等于0嘛
对吧如果说满足这个条件的话
DV等于do
加w
对不对
松弛操作哎
这就是松弛操作
那这样的话我们的算法也就结束了
非常非常简单啊哎
简单轻妙精妙轻巧
让我们来看一下这过程啊
过程的话我们再过一遍
一定就是你懂了这个过程
这个代码你再去写的时候呢
就更加简洁啊
就更快捷
如果说你这个过程掌握不了
你光想去背代码哎
vs等于几来着
是等于一还是等于0来着
对吧哎
松弛操作什么意思来着
你都稀里糊涂的话
那你这个代码肯定你也写不出来
因为这些代码量相对来说要大一
些不是那个什么
你比如说扫他怎么用
我背过他就算了啊
就那么几个字
你看这么长的代码后面还有更长的
你必须得理解他的过程充分理解啊
你才能写出来
像前两天
我做了道别人出的题写了200多行
啊对真的是200多行
你如果说不理解这个
代码的这个执行过程啊
那那那么多行代码你说哎我背过他吧
那肯定是不现实的啊
肯定是不现实的
好那这样的话我们就写完了哈
那么这个过程的话呢
其实第一步
说实话哎这里有个地地方没写
同学们哪个地方错了
哎对
是不是DS
等于0没写啊
对不对是不是
先出手啊自己打直
然后自己到自己本身的距离
为0 然后执行执行TN次操作
每次呢
把点从t集合移动到s集合当中去
对吧然后第一步找最短的那个路径
找最短的那个点
就是找对短路径的那个点
然后找到这个优点以后呢
把优点呢移动到
s集合当中去
移动过去以后呢
再去对这个点所有的相应的边呢
进行松弛操作
就是这么简单啊
就是这么简单
让我们测试一下
哦错了我哪错了同学们
坏了讲了这么大半天还错了好神奇
哦这个地方
这个地方的话
我们是不是要求
插到t集合里面的最短边
对吧
我们要求
s集合与
t集合
就是中间这里边的最短边对不对
你不能求
如果说我d
我DS已经求得了
我是不是就可以更新
DS啊对不对
就是我
我要求的是s与TG和这一些的最大边
就这里边的最大边
而这里面的最大边我们是不关注的
啊
那去哪了
就这里面的最短边
我们是不是不关注啊
因为你这个最短边
是不是这一部分有最短边
这一部分也有最短边
我们关注的是到
这一个点集合的最短边
所以呢咱在这里应该怎么加怎么改
奥特曼
到t集合的最短边
应该怎么改呢
同学们你看怎么改呢
同学们有没有人能告诉我
小张
能不能告诉我
哎小吕在说话小吕
在哪一行
我要看一下DRI哪一行
这个不知道
啊你真是真是在茅台小张呢啊啊
继续茅台
大吕
大吕不知道坏了
胡家玉呢
嗯啊你也不知道
你知道啊
我我啊同学们
我们这个地方哪错了
我们要求的是
到这一个集合的最短路啊
你看看是不是
我们
是不是有可能会访问到这个集合的
那我们如何
避免我们不访问这个集合呢
在哪一行呢
啊小腹啊
67谁谁在说哎6767怎么改呢
啊并写VR
什么
等于等于
0是不是
等于等于0是不是确保我们访问的点
这一点是t集合的点
对不对
我们是不是把它分成两个集合嘛
我们是要确保访问是t集合的点
能理解吧同学们
能理解吗
小赵理解了吗
小赵不想理我
哈哈哈
对不对VIS是不是g
等于0的话表示的是t几何的点哦
对吧因为我们要求的是
点
到所有t集合里面的最短最短点了
最短点了
然后再试一下
哎这回就对了看到吗
嗯测试一下
直接提交一下就行了
过了吗
厉害是吧
你做对了吗同学们
Frank在楼当中已经做做完了
没有电脑给你用了
你看你们这些同学一个个都不带电脑
这边有哦
那边有一台那边有一台那个不
太好使闷气
不好意思
给你找找电源吧
怎么样他们
都忘了吗
我们检查一下啊
哎吕宁对了
好的
复制谁的
复制我的
你从哪复制的
那你也复制不了啊
这是m条边
对不对
我们是不是n表示的是点的个数
边的数量是m
还有谁提交了
哦这是张雨琪的刚张雨琪是m条片
空格
大吕的
你的天
妆太白是吧
后来看见妆太白是吧
为什么会开rap买入呢
那个你测试怎么做的
没有啊没有啊你不用啊哈哈哈
为什么会出现人太排弱运行时错误
运行时错误要么速度越近
什么叫数太大了
哪个数太大
这个没关系吧应该PHDWT
一个0剩下的全都是
25
还不对吗你
Rotan l就很离谱你知道吧
你重测一下
嗯果然还是Rotan l
3371来算
sentiment fought文字
访问访问内存啊
哎这不是你的
我也不知道你哪错了
然后我下载个QQ
你也错了
啊
这是不是鱼也挺小的呀
这咋搞
是我的第三单
老师自己下
载了那个21的数据竟然还是对的
本地测试是对的
本地测试是对的对
本地测试是对的
你把你的nm改小一点
然后再再提交一下吧
改成115老师你看数据要求吧
啊我也没看着你哪错来反正
你赶紧先编译错误就不给看了啊
所有的编译错误一律不看啊
一律不看编译错误啊
啊什么时候变
一出错
是不是该自杀了
这个是谁啊
赵雨欣也是这个
赵雨欣跟他谁
你也改一下这个nm的范围看看吧
哎好像你跟我一样的是吧
对啊
好像你是跟我一样的
为什么你们错了呢
d s等于0
d什么等于0
d s等于0
应该是
什么错了吧
老二改小子改小孩DS
为什么要在这改下加个DS等于0呢
啊这位先
你为什么要在这里给DS改成0呢
DS等于0应该在这吧
是不是
我突然好像知道那个谁
韦德hold怎么错的了
我看看他是不是这样
DNA等于他没错
嗯
神奇的错误
no是渣男
你能帮我看看
啊说呢老师这不
啊还是不对吗
老师我把我的跟你的对比
啊
张晓彤张晓彤
数据范围太小了
嗯有吗
又开小了点还是
热心过了袁艺轩
连袁艺轩都过了
笑一下哈哈哈
好的复制粘贴了吧
我跟你说大家好你要在那什么
我跟你妈说
上课不干正事
啊
嗯我是把数据扩大还是不行
啊还是不许缩小
我是不大
我缩小了也不行
我为什么不行
你也不行
你还不行啊
好神奇我给你给你的看了
我说这平衡器是不是看脸
这玩意估计就不够
是不是随随机装
随机装太白是吧对
啊
你自个到CR提交呢
这个不是炸了吗
没有啊DNN是什么鬼玩意
为什么这出了个n啊
这谁啊
张宇彤为什么有个DN啊在哪里
不是你们自个能不能检查一下
为什么你能看到他的眼袋吗
我也不知道咋按错
UVW耶斯特拉
这这叫什么这叫
什么大家来手后门阶段了
你教错题了人类
3371你教的哪个题
那就可以你上面写的那个啥
我不知道这个女的后哪错了啊
有时候可能
这个对平台机都知道他这个
得得天才输
真的我看没看出他哪错了
哦哦对对对哦
你们是不是能看其他人代码啊
我们这个月
为什么我在看我的
哈哈哈
从哪看啊
从这下面看
对我给你们开的权限是吧
太牛逼了
我也我也不知道怎么做的
吕德宏你怎么错了
我也不知道
你能看得出他的问题吗
哎路虎挑了多少一个老师
三三十吗
算了就这样吧
好吧三七就这样吧
三七什么
三三七哦行那么我们继续吧
还有20多分钟
我们还能再讲一个他的优化好吧
这个下一再讲的时候
那个十一就得跟上了啊
那个
附加于啊
不用填那样填
没关系一会我们就用Wifi去做啊
好同学们我们来分析一下它复杂度吧
来分析下复杂度啊
我们来看一下
找一下我们的代码啊
同学们我们这个DJ斯特拉索道
我们可以看到哈
最外层循环是执行n次
因为我们要执行n次移动操作是吧
是不是移动n个点执行n次操作
所以我们最外层循环是不是o n的
那么每一层里面
我们是不是要去执行一个操作
第一步找对小o n吧
对不对第二步是移动o e
第三步
是不是访问所有的边
访问所有的边
假如说是k
每个边有k条边
那n n乘以k是不是正好应该是等于m
对不对所以的话
我们这复杂度的话应该是欧恩方
加m
而我们又通常认为
这种简单图是没有字环和重边的
所以n个点最多有多少条边呢
比如n乘以n减一条边
有像图对不对
所以我们这个n方是不是应该大于m
啊
对不对
所以我们认为我们的复杂度呢
是o n方的
DS达拉算啊
朴素的DS达拉的复杂度是o n方的
能听懂吗
同学们
那么现在我们来考虑优化
这个复杂度听懂了吗
二八来赵雨欣
复杂度是多少
OOO什么
o n的38
好好
可见你们
卢文芳加m啊
你们上课都在干什么
认认得同听吗
我们的复杂都是怎么算出来的
完了
你们假装在听课吗
这不是你说
老师
辛辛苦苦的给你们这个充分的备课
就防止今天这节课给你们讲不明白
结果你们热到
好
啊好真好是吧
结果你们你看看你们
啊
这假装假装在听课
傅嘉玉我们的苏打都是怎么算出来的
哦因为n乘k
n
小于n方
所以去那个最大
n乘k其实就是防每个点的边吗
每个点的边加起来不就是m吗
对
n方加m对
然后因为是简单图
简单图的话最多有n乘以n减一条边
对不对
所以m的话是不是就小于这个东西啊
小于等于这个东西啊
所以最终的话
复杂度是不是很方的复杂度啊
你说说你们
大家好听
听懂了吗
你问我呢
哈哈哈你问我呢
哈哈哈
我是听懂了你听懂了吗
王一正你听懂了吗
嗯哈哈哈听懂了但是我完全知道啊
对所以你只要问我我就没听懂
你不问我我就听懂了是吧
这叫什么
什么什么的猫来
那个叫薛定鳄的猫
对薛定鳄的猫啊处于一种未知状态
哈哈哈未知状
宇宁应该听懂了吧
你们听课要认真哈
是吧刘子君
听懂了吗
我们的复杂度的分析
也是薛定额的猫也是薛定
薛定额状态属于未知状态
你哎呦富家玉不是飞翔笑的这么嗨
肯定听懂了
这个不给你们浪费时间了啊
我们来看一下啊我们
啊对啊
我们来看一下
我们来怎么去进行优化啊
我们现在是
这样一个复杂度对吧
这样一个
复杂度那么在这里找最小的时候呢
我们采用的是o n的复杂度
访问了每个点
那这个地方的话我们是
不是就可以构造一个优先对列啊
构造一个优先对列
那是不是就可以OE的去访问了
访问最小了
对不对但是呢
我们
我们在对他进行松弛操作的时候呢
因为在维护这个优先对列吗
我们在这里是不是需要加一个log
n的复杂度啊
所以最终的话应该是m乘以log n
复杂度
也就是说我们如果对它进行优化的话
就m乘以log n的复杂度
不是越优化越
越优化越大
啊啊
啊
原先是n方加m吗
现在的话是m l n l n加一啊
等等我看我们有没有讲错啊
别给你们讲错了
m log m
m log n
对应该就这样这样一个四大读完了
优先对叠里元素的个数o m
对我们这个的话是m log m
就是我们在维护的时候呢
是因为最多呢有可能有m个
这些点呢有可能加入m次
哎是这个样子的m乘以logo
当然这是最
这样的话不是应用或者是他吗
我认为m log
然后另一个大哥
把这个
这个这个
我们看一下啊
不同的
实验方案
暴力暴力的话是这个啊
二叉堆我们用优先对列是这样的
在稀疏图当中
你看哈在稀疏图当中的话m约等于o n
假如说他告诉你这个图是稀疏图的话
因为
正常情况下他不会给你摁个点
然后给你摁方条边
他就是1亿4的点他不可能给你1亿8的点
正常情况下
所以我们通常情况下
处理的其实都是稀疏图哈
但迪迪斯特拉的话算法的话较为优秀
因为而在稠密图当中
是m约等于欧恩方
稠密图的话就是就是接近于恩方了
那这时候的话就
就显得不是那么优秀了啊
就不显得不是那么优秀了啊
所以的话我们啊采用优先对列去优化
这时候的话
吸收图当中n m的话约等于n
所以最终的话就是n落个n
你可以这样理解
对吧因为正常情况下都是稀疏土耳
我们现在所有见到的土基本上就是
呃你只要恩很大
他绝对不可能给你恩方条边
你如果说1亿4的
嗯他就不可能
你不可能说是获取1亿8的币
你知道吧
对吧
若是一一5的点你更得不到一一10的点
对不对所以
正常情况下我们做的题都是稀疏图
如果说他说我给了你一个图
请对他的补图
求队友路径
补图其实就是他
给你哪些边就表示这些边没有
剩余的那些是有的啊
啊对啊那这时候的话我们可能就需要
啊进行这个
这这这这个这个这个
如果是这样一个题目的话
我们就选择放弃是吧
啊选择放弃啊
好了我们不说了
我们来看一下怎么优化啊
优化的过程的话其实非常简单就是
维护一个最小的维护一个
优先队列听课吕德谦
听课吕德谦还在踢球rotamina
哈哈哈神奇的rotamine听课好好吧
同学们听课哈
我们要维护一个优先对列这个优
先对列的话
他的最小值呢就在堆点就在这个
啊就我们可以用OE的方法
去访问这个最小值吗
所以我们就把这个变成OE了
然后呃把它从t集合拿到s集合当中
也是OE
然后呃改的
其实呢
就是在这里去松弛操作的时候呢
有一个维护
维护有限对列的过程
啊松弛操作啊
所以呢我们
目标目标的话就是加上这个东西
加上这个东西然后还有一个
就这样吧
就是我们在这里的话
我们有可能
就是我们加的时候
有可能加了好多次啊
是不是所以我们也
不是固定的循环n次了
而是当我们对列为空的时候结束
就是我们这个地方的话
并不是固定循环n次
因为有些点有可能
你是已经求的最短路了
比如说你已经求的他的最短路了
比如说4点已经求的最短路
但是他有些在松弛的过程当中
他又给你加了好多次
加了好多次
哥你比如说
这是优点
我们经过x点到u松弛了一次
经过y点到u又松弛了一次
经过z点到u又松弛了一次
对吧那假如假如说我们每松弛一次
我们都入
都加入到我们的堆里面去一次
那
它在我们的堆里面是不是就有多次啊
所以最终的话
我们这个地方的话
不是执行o n次操作
有外层循环的话不是执行o n次操作
但是几乎约等于o n次操作
因为如果说我们访问出来的点已
经访问过的话
我们就不再进行松弛操作
所以呢这个地方的话
就几乎约等于o n次操作
好那么我们去做一下
我们新建一个嗯
我们新建一个吧
这个这个地方的这个4779啊
表示的是他的困难版
比如说这道题哈就是
但这两路径的这个优化版本
比如说如果说我们的复杂度比较高
我们就需要用到这个
啊对优化去做这个题了啊
所以呢我们去做一下
就是4779这道题也就是我们题库当中的
51题 51题啊
那么这一道题的话
我们采用的是连接表的方法
用连接表去做啊
因为连接表的话
我们需要构造一个结构体是吧
对不对
啊一个是我们的点的
点的什么
呃下一个点
two
wait
这题告诉我们是115是吧
115的话我们就
哎我把水倒哪去了
你把我水吐吐这
了
怎么样朋友们
到这一步应该没问题吧
然后相似
相似到我们底下的话应该也是
看不清吗
啊应该还是这样一个样的啊去做
DJ斯塔拉
同学们
这个也要做笔记的哈
啊今天
我们可以说是真的是每周一个算法
你把这些笔记做好了
你这这真的这你不用说多了
多说了你一个月下来你都进步飞快
更别说你这个一年下来
而且你看我们假期又要集训了
吕宁去日照吗
不去看来
啊
好了那么我们看一下啊
还是一样的操作
我们这里的话需要维护两个对啊上
一道题我们有个Pro也没有用啊
对不对还记得吗
普瑞的话其实非常简单
就是在这个更呃松车的时候呢
普瑞v等于优点上
我的v点更新是从优点更新来的啊
到达v的
到达v的路径
是从u来的
对不对比较简单啊
那这样的话
假如说你遇到一道题目
要求你求对短路径
上的点
那我们就会做了是吧
IF这个地方它有没有告诉我们什么
因为确保
到每个年纪
不能保数据保证你都能到达是吧
数据保证
并且这个地方的话
c个嘛W I
小于小于呃10的9次方
也没有问题是吧
c个么大不大小于10的9次方
那这个地方的话就就
就这样就行了
在这里的话我们说了
我们维护的是一个堆
既然是一个堆我们就应该有一个堆
对不对
那这个堆里面的话应该存储两种信息
哪两种信息呢
一个是点
还有一个是距离
也就是说
d点u还有DU
所以呢我们需要再构造一个结构体
其实这个结构体跟这个结构体可以
共用可以共用啊
但是
我们为了清晰
我们就不共用了啊
就是说这两个其实是没有关系的
你只是说哎这两个
这个点也是有一个点一个距离
我们这个也是有一个点一个距离
可以说是用一个结构体去做
但是我们我们不这样干是吧
啊point点
距离
啊注意同学们
我们在这个结构体当中是可以重载运
算符的
如果说我们想构造一个堆
它里面必须应该要有这个
小鱼号
也就必须应该要有这个操作符小鱼
所以呢
我们必须要构造上这个小鱼这种操作
也就是说我们的充载云探符
因为我们默认情况下是大颈椎
所以我们现在要维护一个小颈椎
就应该是d
大约b点d
勾到一个小顶堆的节点
这个的话其实就是勾到一个小于号
也就是说我们两个
两个结构体是可以进行大小比较了
这个我们假期的时候
找个机会再讲一下吧
这个你先抄上吧
见过吗小张见过吗
你你见过自己都写过是吧
你见过吗
嗯现在这个CONS是来修饰这个b的
也就是说
我们两个结构题要进行比较吗
第一
这个CONS修饰的是你要比较的对象
是b
这个cos修饰的是你自己
cos表示的是常量化
也就是说你是不能被修改的
比如说你自己还有这个
被比较的对象b
两个都是不能被修改的
那这样的话我们就可以勾到一个堆
在里边free
oraty
构造一个对列
优先对列
然后呢当我们对列飞空的时候
我们不停的去找这个堆里面的最小
最最小值是吧
啊找到对顶元素
找到最顶元素
OE的操作就找到了
也就是它的点是多少
嗯q点后方弹出
如果优点的最小值我们已经找到了
我们是不是就不要再操作了
哎如果最小值已经找到了
就不要再去对他进行松弛操作了
也就是说
如果他已经加入到s集合当中了
对吧如果已经在s集合当中
那这个点我们是不是不用操作了
只有是在第几个当中的点
我们才把它拿进去对吧
如果已经在s集合中
就不要操作了
只有在t集合中的点
我们才拿进去
然后松弛对不对
是吧如果已经在s集合当中了
那这个点就不需要再操纵
好那么拿过去的话VSU等于一对吧
啊four
错了应该是DV
并且我们要加上
如果在t集合当中
如果这个点在t集合当中
也就是跟u相邻的点在t集合当中
并且可以松弛的话
那么松弛
松吃完以后再把它入队
啊这是靠top
应该是top不是for
做错了
啊因为
我们第一个点应该要入对
啊做对了
嗯对吧
这就是我们的对于画的DJ斯特朗
我去提交一下看一下
省的你们省的做错了丢人
我偷着自个教你们别看
嗯哎做对了啊
好我们把这个过程呢
描述一下
对优化的DJ斯塔拉
那它跟我们刚刚的朴素的DJ斯塔拉
区别呢就是
我们希望在
就是找这个最小值的时候呢
不要o n的方法去找了
而是维护一个小顶堆
维护一个小顶堆
然后呢直接O1的操作找到
所以呢我们就应该有一个堆
那这个堆的话
它的元素节点
的话呢就是要维护两个信息
我有两个星期
一个星期的话就是点点是谁
再一个星期的话
就是到这个点的距离又是谁
然后呃如果有小小小顶堆的话
那么我们的写法对吧
如何构造结构体
然后构造一个优先对列
学过吗这个学过吗同学们
没有
放学过了是吧
放在暑假里吧
这个我们回头可以写一下
这个堆是怎么构造的
这都是这些知识点不是很重要
所以呢学不学都行是吧
啊爆循环
去更新一下去
就是做一下初始化
然后DS等于0
pose把把这个点
先把原点pose进去对吧
啊当堆堆飞空的时候呢
我们去不停的访问堆顶元素
堆顶元素的话其实就是最短的那条边
然后pop出去
对吧然后
如果这个点已经在s集合当中的话
我们就不不操作
否则的话
我们说明他在t集合当中
把它拿到s集合当中去
拿进去以后呢再进行松弛操作
松弛完之后呢
再松弛完之后呢还要对他进行一个
维护哈在对待
这个因为我们有一个优先对列嘛
要把这个元素呢
插入到我们的优先对列当中去
这也是我们的啊过程哈
同学们提交一下提交一下
都做对了吗
哎张瑞琪做对了
你们可以就是做
在做笔记的时候参考我们
我的代码也可以参考那个OIVK
去做一下啊
哎也也讲不了多少东西啊
就是一个半小时吧
确实是只能说讲讲算法做题是够呛
没时间做题
所以你们暑假
的班一定应该问题不大吧
报告啊同学们在座各位
抱抱
啊
你爸爸说给你抱那你妈妈还没同意呢
好的
飞翔呢
抱不抱我就很奇怪你们
现在你们家长也不联系我
让他们尽快给我答复
小猪呢
应该是抱啊
不报我就不开了
不不不讲了我光光讲入门课就行了
好吧咱们这个课这么难还得备课
好吧同学们
哈哈啊然后接下来的话就是
没有人提交的吗
就这么三个两个教的
认得同根一错误
检查一下里面的博客吧
51题啊愚蠢的人类
你还有呢
张雨桐朱洪轩戴佳昊傅以翔王秋俊
任德通赵雨欣王一正
刘子金
李林梁一山崩看了肯定没写
吕德浅张瑞琪
没有了哈
步行DP
这上周那个克鲁斯卡尔去哪了微信
朋友圈
因为充分理解啊充分理解
因为克罗斯卡尔是属于
是比较简单的写法啊
逛游乐园
既然博客都写了
就把那个什么视频录一个吧
啊
我们这是那个什么北辰卫绿月的视频
我还没录着录呢
啊陪床陪了一个星期
上周五开始
陪到陪到昨天
然后是
大家好
提前把下周的作业做完他说
防止下课讲课的时候上课之前忘了做
飞翔我靠你俩是一样的啊
什么一样
代码字知道了啊对代码是一样
哈哈哈
丹彤
丹彤我没写啊我在下边啊在下边
那在下边
哪有啊图论的下边
哦在图论的下边
啊
还可以吧
这节课听懂了吗
认得同
赵雨欣哎呦
还还order的卖
这个这个不是我们
上去年10月份讲的吗
嗯对不对
对啊那怎么现在做呀
也还行吧
叫虚尔世奇之是吧
你们不都是一个图啊
哎还行啊
证明了真的会证吗
王一哥王一证真的会证明了吗
啊真的会证明了吗
呦刘子经也坐上了证证明能证吗
能证吗
DJ Las DJ star最早生日说什么
三个小时之前的
嗯三个小时上课之前
哈哈哈 14点2点钟的时候开始
哎
很奇怪你最小声的时候
怎么画了个最短路的图啊
为什么那么短
真的
啊这这是最小声的图
啊绿的浅然后我直接放图到下边啊啊
真的假的
为了防止老师检查的时候临时
把作业加上
所以呢
放在评论里边别让老师发现
机智
啊
嗯这两天出去的时候时间紧
对
好
你们得把这个最重要的就是过程啊
证明都是次要的
你得把过程理解透彻
然后你们做完作业的话
也可以适当的去做一点题目啊
就我们的题目的话
其实都在这上面写着
啊在我们那个
你看啊
我们这里呢有第七章求最短路径
第八章求最短路径第九章求最短路径
这3张都是最短路径你都可以做啊
啊你都可以去做啊
都搜索
出来之后呢
这其实就是为你们暑假所准备的
准备了各种各样的训练计划
还行吧同学们
题目都已经很多了很丰富了看到吗
好咱们咱们今天就到这里了
我知道你们这个意犹未尽
哎呀老师讲的太好了再讲两句吧
那我就再讲两句
好吧那就先这样吧
拜拜关机
试过了吗你就说不可以
这网上没有那种写法
那你为那你为啥不试一下呢
那还是不行啊
你爸错了
你以后你就得比他强
你说你错了
应该是这样
啊
条件十分艰苦
啊 300多人一个班吧
你们你们
啊是有350的有400的
好像有三百
你报的是几百的
你报没报
你报了你报了你报了
再见反正不是我教
不会是
XN吧
不可能他在一一中上
跑他跑日照去
一个眼神看的我心里发光
为什么不好
哎从什么时候开始呢
对乃反正
10点就是弄个就是下午
因为如果说光下午是吧
我下午吧
下午时间长啊上午时间短
上午时间咋的了
下午是就是
以做题为主是吧
知识加做题
讲课还是做题
讲课加做题
内容加做题
其实
这题做完之后应该是题目
得了你如果光听做不做题
你看好像这个题还是个题
干嘛你在干嘛
哈哈哈
我看看其实我我喜欢的是
那好多人去日照
如果说
如果说你知道的不是很多咱就按照
对如果说确实要的人很多
不行还得收不到
是吧
你你你你那个啥是是什么你不要
你那个上午没别的
啊上午还有别的班
是吧然后下午的话上午是什么
上午是
刷题班刷刷简单题
那他他呢他下午
是啊你们你你以前不做过吗
还是刷那个
比他们那技术差的刷那个比较合适
像像咱们这个班
他现在那个谁那边是啊那边讲的那个
你掌握那个他已经掌握了