12.25模拟赛T2
2024-09-01 06:14:44
https://www.luogu.org/blog/a23333/post-xing-xuan-mu-ni-sai-path-ji-wang-zui-duan-lu
如果设f[i]表示从i到n的期望
那么转移方程比较好列。
但是取min的环形转移？
反过来想，
如果我们知道了f[x]的大小关系，
其实，可以化简成
其实就是，我们把一些min变成f[x]然后再消一消。
其实转移貌似没有环了？
但是我们不知道大小关系。
一些边没有用，度数减少一些。
只有比f[x]小的f[y]会转移到x，感觉和最短路有关？
实际上，
把f[n]=0放进堆里，跑一个堆优化dij，每次取出最小点更新相邻的点的f值。
用分析法或者加权平均数可以证明:f[x]<f'[y]<f[y]
所以，这个转移是有意义的，并且转移完成之后，f[y]不可能比f[x]小使得转移变得不合法
而且，可以证明，一个f值被取出的第一次，就是最终的f值。因为能转移到的一定都更新了，不会越更新越小导致能再转移过来。
然后开心dij一下即可。
不放心的话，可以观察最后的实际转移情况，所有转移一定是从比f[x]小的地方转移而来。
最新文章
- [已解决] C3p0连接配置
- mysql mybatis-generator plugin 分页
- OpenCV 2.4.11 VS2012 Configuration
- 【转】轻松搞定FTP之FlashFxp全攻略
- 你用什么方法检查 PHP 脚本的执行效率（通常是脚本执行时间）和数据库 SQL 的效率（通常是数据库 Query 时间）， 并定位和分析脚本执行和数据库查询的瓶颈所在？
- 将JSON数组显示前台Table中
- TIKV副本一致性检查机制分析
- C#之结尾篇
- 关于Python的一些看法
- Apache启动不成功时，用命令行检测（新手)
- Feel Good POJ - 2796 （前缀和+单调栈）（详解）
- OnCheckedChangeListener和setChecked之间冲突问题解决
- 5款最好的免费在线网站CSS验证器
- 动态添加 SqlParameter 参数
- NSTimer+倒计时功能实现
- 准备mysql-connector-java
- 正则判断 文件名是否为zip格式
- noip第4课资料
- 【代码片段】Python发送带图片的邮件
- c++ 声明和定义的区别