[BZOJ 3143][HNOI2013]游走（数学期望）
2024-08-25 18:04:21
题目：http://www.lydsy.com:808/JudgeOnline/problem.php?id=3143
分析：
易得如果知道了每条边经过的数学期望，那就可以贪心着按每条边的期望的大小赋值，所以问题就是如何求每条边的期望。
直接求没办法求的，可以先求出每个点经过的期望。
易得f[i]=∑f[j]/d[j] j->i有边
特殊的，对于起点，因为刚开始就在，所以应该是f[1]=1+∑f[j]/d[j]；对于终点，到了终点后不能再到其他节点，所以对其他边并没有贡献，所以f[n]=0
然后就可以高斯消元解方程组，解得每个点的期望
那么对于边(u,v)，这个边的期望（即经过次数）就是f[u]/d[u]+f[v]/d[v]
那么对于每个边的期望排序，期望小的对应编号大的，计算一下就行了。（排序不等式）
最新文章
- SQLite剖析之编程接口详解
- SQL 会议消费记录统计
- ios 实现版本更新检查
- mysql取出现在的时间戳和时间时间戳转成人类看得懂的时间
- 向Array中添加希尔排序
- 清除SQL Server执行计划
- Delphi生成GUID
- Linux进程笔记
- Mac入门推荐（写给Mac小白）
- 初学Python（九）——函数
- javascript之复习(css属性值的计算)
- 【BZOJ5110】[CodePlus2017]Yazid 的新生舞会
- 利用Mega2560实现USB转串口
- JAVA虚拟机体系结构JAVA虚拟机的生命周期
- python计算机视觉项目实践
- Matlab 编程
- windows下如何下载并安装Python
- 【C#/WPF】用Thumb做可拖拽的UI控件
- windows安装logstash-input-jdbc并使用其导入MMSQL数据
- php_memcahed 安装