期望应用

有向图

例题1 洛谷-P6154 游走

• 统计 + 计算概率
• 拓扑排序
• 类似前缀的统计路径总数量、路径总长度
• 然后直接求期望

例题2 洛谷-P4316 绿豆蛙的归宿

• 期望 dp
• 拓扑排序，做期望 dp

注意期望 dp 一般是倒着做，这样思路会更加清晰

• 这一题就需要注意倒着做，不然会 WA
• 这里的 \(dp_i\) 表示从 \(i\) 倒 \(n\) 所经过的路径总长度期望
• 设在有向图中 \(u\) 可以到达 \(v\)
• \(dp_u = \sum_{i=1}^{k}{\frac{dp_{v} + w}{cnt_u}}\)

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 3;

struct Edge{ int x, w; };

int n, m, Nxt[MAXN], cnt[MAXN];
long double dp[MAXN];
vector<Edge> eg[MAXN], son[MAXN];

void dps(){
  for(int i = 1; i <= n; i++) Nxt[i] = max(0, int(son[i].size()));
  vector<int> stk;
  for(int i = 1; i <= n; i++){
    if(Nxt[i] <= 0) stk.push_back(i), dp[i] = 0;
  }
  while(int(stk.size()) > 0){
    int i = stk.back();
    stk.pop_back();
    for(Edge j : eg[i]){
      dp[j.x] += (dp[i] + j.w) / cnt[j.x];
      if(Nxt[j.x] > 0){
        Nxt[j.x]--;
        if(Nxt[j.x] == 0) stk.push_back(j.x);
      }
    }
  }
  cout << fixed << setprecision(2) << dp[1];
}

int main(){
  cin >> n >> m;
  for(int i = 1, U, V, W; i <= m; i++){
    cin >> U >> V >> W, cnt[U]++, swap(U, V);
    eg[U].push_back({V, W}), son[V].push_back({U, W});
  }
  dps();
  return 0;
}