P4316 绿豆蛙的归宿

题目

P4316 绿豆蛙的归宿

算法标签: 期望$dp$, 树上$dp$, 拓扑排序

思路

设$f[i]$表示点$i$到达点$n$的期望路径长度, 设点$i$的下一个点是$j$, 那么状态转移就是$f[i]=p\ast f[j]+w$, $p$是点$i$走到$j$的概率, 通过刷表进行状态计算

记忆化搜索代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e5 + 10, M = N << 1;

int n, m;
int head[N], ed[M], ne[M], w[M], idx;
//f[i]表示从节点i开始到节点n的期望
double f[N];
int deg[N];

void add(int u, int v, int val) {
   
    ed[idx] = v, ne[idx] = head[u], w[idx] = val, head[u] = idx++;
}

double dfs(int u) {
   
    if (f[u] >= 0) return f[u];
    f[u] = 0;
    for (int i = head[u]; ~i; i = ne[i]) {
   
        int v = ed[i];
        f[u] += (dfs(v) + w[i]) / deg[u];
    }

    return f[u];
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    memset(head, -1, sizeof head);

    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
   
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);
        deg[u]++;
    }

    memset(f, -1, sizeof f);
    dfs(1);
    printf("%.2lf", f[1]);
    return 0;
}

拓扑排序代码

反向建图, 使得$n$最终指向节点$1$, 拓扑排序从节点$n$开始, 假设下一个节点是$v$, 那么就能从$f[n]$递推到$f[v]$, 那么状态转移就会变成$f[v]=(f[n]+w)/deg[v]$, 然后减少节点$v$的度数, 如果节点度数$=0$, 将当前节点加入到队列

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e5 + 10, M = N << 1;

int n, m;
int head[N], ed[M], ne[M], w[M], idx;
double f[N];
//o_deg是拓扑排序使用的, deg是计算期望的
int deg[N], o_deg[N];

void add(int u, int v, int val) {
   
    ed[idx] = v, ne[idx] = head[u], w[idx] = val, head[u] = idx++;
}

void top_sort() {
   
    int q[N], h = 0, t = -1;
    q[++t] = n;
    while (h <= t) {
   
        int u = q[h++];
        for (int i = head[u]; ~i; i = ne[i]) {
   
            int v = ed[i];
            f[v] += (f[u] + w[i]) / deg[v];
            if (!(--o_deg[v])) q[++t] = v;
        }
    }
}


int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    memset(head, -1, sizeof head);

    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
   
        int u, v, w;
        cin >> u >> v >> w;
        add(v, u, w);
        deg[u]++, o_deg[u]++;
    }

    top_sort();
    printf("%.2lf", f[1]);
    return 0;
}