2018.07.22 洛谷P4316 绿豆蛙的归宿(概率dp)
2024-08-21 15:15:01
传送门
简单的递推。
由于是DAG" role="presentation" style="position: relative;">DAGDAG,所以状态转移方程很好写。
一个点的答案等于所有能到的点的答案加上所有边权再除以边数。
没理解的请看代码:
#include<bits/stdc++.h>
#define N 100005
#define M 200005
using namespace std;
struct Node{int v,next;double w;}e[M];
double dp[N];
bool f[N];
int cnt=0,first[N],tot[N],n,m;
inline void add(int u,int v,double w){
++tot[u];
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].next=first[u];
first[u]=cnt;
}
inline double dfs(int p){
if(f[p])return dp[p];
f[p]=true;
dp[p]=0.0000;
if(p==n)return dp[p]=0.0000;
for(int i=first[p];i;i=e[i].next){
int v=e[i].v;
dp[p]+=e[i].w+dfs(v);
}
dp[p]/=tot[p];
return dp[p];
}
int main(){
memset(tot,0,sizeof(tot));
memset(f,false,sizeof(f));
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
int u,v;
double w;
scanf("%d%d%lf",&u,&v,&w);
add(u,v,w);
}
printf("%.2lf",dfs(1));
return 0;
}
最新文章
- [Hadoop大数据]——Hive部署入门教程
- 部署私有的Nuget服务器
- 管理分支:git branch
- 《静静的dojo》 总体教程介绍
- git技巧记录--blame
- ATI Radeon HD 5450 with full QE/CI Support ( 转载 )
- OAF_EO系列1 - Definition定义(概念)
- Linux基本命令 目录
- centos Supervisor
- C3P0连接池配置方式
- List<;T>;类
- RH253读书笔记(9)-Lab 9 Account Management Methods
- TCP/IP传输层,你懂多少?
- MediaScanner
- C# 7.0 新特性:本地方法
- Tomcat 设置开机自启
- 中国省市县数据库sql文件(2017年10月31日之前)
- CustomScrollView
- IDM的Google商店插件
- python 文本分类