基础数学算法-绿豆蛙的归宿

题目-绿豆蛙的归宿

问题分析

图的性质是, 从起点开始能到达图中所有点, 图中所有点也能到达$n$号点
如果遇到岔路, 会以等概率跳到下一个位置, 要求计算的是路径的期望

因为初始状态是唯一的, 下一个状态不唯一
因此可以定义状态表示$f(i)$, 表示从$i$到终点的路径期望, 初始状态是$f(n)=0$, 目标状态是$f(1)$

对于当前位置$u$如何计算$f(u)$?
假设$w_i$是边权, 根据期望的性质
$$f(u)=\sum _{i=1}^k\frac{1}{k}\cdot (f(s_i)+w_i)$$

算法步骤

算法只需要实现上述的公式, 从后向前递推, 因为是拓扑图的递推关系, 不存在环

• 首先计算拓扑序
• 按照拓扑序计算状态$f(i)$

因为每个点只会被考虑一次, 算法时间复杂度$O(n)$

代码实现

$top$排序 + 逆序递推代码

#include <bits/stdc++.h>

using namespace std;

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

int n, m;
int head[N], ed[M], ne[M], w[M], idx;
int din[N], dout[N];
double f[N];
int q[N], h = 0, t = -1;

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

void top_sort() {
   
    for (int i = 1; i <= n; ++i) {
   
        if (!din[i]) q[++t] = i;
    }

    while (h <= t) {
   
        int u = q[h++];
        for (int i = head[u]; ~i; i = ne[i]) {
   
            int v = ed[i];
            din[v]--;
            if (!din[v]) q[++t] = v;
        }
    }
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.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;
        din[v]++;
        dout[u]++;
        add(u, v, w);
    }

    top_sort();

    for (int i = t; i >= 0; --i) {
   
        int u = q[i];
        for (int j = head[u]; ~j; j = ne[j]) {
   
            int v = ed[j];
            f[u] += (f[v] + w[j]) / dout[u];
        }
    }

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

记忆化搜索实现代码

#include <bits/stdc++.h>

using namespace std;

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

int n, m;
int head[N], ed[M], ne[M], w[M], idx;
int dout[N];
double f[N];

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

double dp(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] += (dp(v) + w[i]) / dout[u];
    }
    return f[u];
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.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;
        dout[u]++;
        add(u, v, w);
    }

    memset(f, -1, sizeof f);
    dp(1);

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