ICPC南京网络赛D.robot

题意:

给定一颗有向无环图，要求从1走到n所需能量的期望，在走到一个点的时候，有相等概率走到随机一条边，花费一天时间。第i天花费i的能量

$$设dp[i]为从i走到n的期望天数 \\ dp[i]=\frac{\sum dp[v]}{d[i]+1}+\frac{dp[i]}{d[i]+1}+1\\ 则我们需要的答案ans[i]从i走到n的期望能量，只要加上走一步加天数的期望，因为夺走i天需要消耗dp[i]的能量\\ ans[i]=\frac{\sum ans[v]}{d[i]+1}+\frac{ans[i]}{d[i]+1}+dp[i]\\$$

代码

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
vector<int> g[N];
double dp1[N], dp2[N];
int n, m, T;
void init()
{
    for (int i = 1; i <= n; i++)
        dp1[i] = dp2[i] = 0;
    for (int i = 1; i <= n; i++)
        g[i].clear();
}
void dfs(int x)
{
    if (g[x].size() == 0)
    {
        dp1[x] = 0;
        dp2[x] = 0;
        return;
    }
    if (dp1[x])
        return;
    double sum1 = 0;
    double sum2 = 0;
    for (int i = 0; i < g[x].size(); i++)
    {
        dfs(g[x][i]);
        sum1 += dp1[g[x][i]];
        sum2 += dp2[g[x][i]];
    }
    dp1[x] = (sum1 + 1 + g[x].size()) / (g[x].size() * 1.0);
    dp2[x] = (sum2 + (g[x].size() + 1) * dp1[x]) / (g[x].size() * 1.0);
}
int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d", &n, &m);
        init();
        for (int i = 1; i <= m; i++)
        {
            int u, v;
            scanf("%d%d", &u, &v);
            g[u].push_back(v);
        }
        dfs(1);
        printf("%.2lf\n", dp2[1]);
    }
}