数学&动态规划:期望DP
2024-10-20 20:36:52
BZOJ3036
给定一张有向无环图,起点为1,终点为N,每个点i有ki条出边,从每个点走其中一条出边的概率是1/ki,求从1到N的期望步数
我们注意到一点,走每条边都是等概率的,那么就相当于
给定一个DAG,随机走,求起点到终点的路径长度期望
那么只需要知道经过每一条边的期望次数,乘以边权之后再求和就是答案了
问题就转化成了,求经过每一条边的期望次数的问题
经过这条边的期望次数就是经过这条边起点的期望次数除以这条边起点的出度
那么只需要求经过每一个点的期望次数
就好了
#include<cstdio>
const int maxn=;
const int maxm=;
int n,m,cnt;
bool vis[maxn];
int g[maxn],out[maxn];
double f[maxn];
struct Edge
{
int t,next,v;
}e[maxm];
void insert(int u,int v,int w)
{
cnt++;e[cnt].t=v;e[cnt].next=g[u];g[u]=cnt;e[cnt].v=w;
}
long long read()
{
long long x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
void dfs(int x)
{
if(!vis[x]) vis[x]=;
else return;
for(int tmp=g[x];tmp;tmp=e[tmp].next)
{
dfs(e[tmp].t);
f[x]+=e[tmp].v+f[e[tmp].t];
}
if(out[x]) f[x]/=out[x];
}
int main()
{
int u,v,w;
n=read();m=read();
for(int i=;i<=m;i++)
{
u=read();v=read();w=read();
insert(u,v,w);
out[u]++; //出度统计
}
dfs();
printf("%.2lf",f[]);
return ;
}
代码风格清新脱俗
最新文章
- swing with transformjs
- python编码
- 中间件、MetaQ入门学习
- Nginx具体的压缩配置
- Unity Fresnel Hero(Dota2) Shader
- [原创].NET 分布式架构开发实战之一 故事起源
- mysql 基础之CURD
- mongodb两次被黑后......
- excel_VB宏脚本_批量生成点餐宝接受的格式
- Java List集合特有方法程序用法
- NYOJ--187--快速查找素数(筛选法,素数打表)
- 总结描述用户和组管理类命令的使用方法,系统用户相关信息,取出主机IP地址
- linux-shell系列6-rundeck生成host文件
- IT界的一些朗朗上口的名言
- select默认选择后台转过来的option选项
- python advanced programming ( II )
- select top 变量问题
- 基于Ubuntu+kodexplorer可道云的私有云网盘
- Android利用广播监听设备网络连接(断网)的变化情况
- GIS 地理坐标分类
热门文章
- 记录 C++ STL 中 一些好用的函数--持续更新 (for_each,transform,count_if,find_if)
- 学习c++ofstream和ifstream
- 01_Java基础_第1天(Java概述、环境变量、注释、关键字、标识符、常量)_讲义
- jQuery异步Deferred
- haproxy入门 (作用: 高可用性,负载平衡和用于TCP和基于http的应用程序的代理)
- 通过js读取元素的样式
- crontab笔记
- 【前端学习笔记】arguments相关
- php 随机密码和盐 来自wordpress
- Eclipse 保存代码时,不自动换行设置