数学&动态规划：期望DP

BZOJ3036

给定一张有向无环图，起点为1，终点为 $N$

$N$

那么只需要知道经过每一条边的期望次数，乘以边权之后再求和就是答案了

问题就转化成了，求经过每一条边的期望次数的问题

经过这条边的期望次数就是经过这条边起点的期望次数除以这条边起点的出度

那么只需要求经过每一个点的期望次数

就好了

 1 #include<cstdio>
 2 const int maxn=100005;
 3 const int maxm=200005;
 4 int n,m,cnt;
 5 bool vis[maxn];
 6 int g[maxn],out[maxn];
 7 double f[maxn];
 8 struct Edge
 9 {
10     int t,next,v;
11 }e[maxm];
12 void insert(int u,int v,int w)
13 {
14     cnt++;e[cnt].t=v;e[cnt].next=g[u];g[u]=cnt;e[cnt].v=w;
15 }
16 long long read()
17 {
18     long long x=0,f=1;char ch=getchar();
19     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
20     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
21     return x*f;
22 }
23 void dfs(int x)
24 {
25     if(!vis[x]) vis[x]=1;
26     else return;
27     for(int tmp=g[x];tmp;tmp=e[tmp].next)
28     {
29         dfs(e[tmp].t);
30         f[x]+=e[tmp].v+f[e[tmp].t];
31     }
32     if(out[x]) f[x]/=out[x];
33 }
34 int main()
35 {
36     int u,v,w;
37     n=read();m=read();
38     for(int i=1;i<=m;i++)
39     {
40         u=read();v=read();w=read();
41         insert(u,v,w);
42         out[u]++;  //出度统计 
43     }
44     dfs(1);
45     printf("%.2lf",f[1]);
46     return 0;
47 }

代码风格清新脱俗