The Preliminary Contest for ICPC Asia Nanjing 2019 D. Robots

题意：给出一个DAG，一只机器人从1点出发，等概率地选择一条出边走或者停留在原点，机器人的第k次行动消耗能量是k(无论是走还是停留都算一次行动)。问1到n的期望。

解法：因为行动消耗的能量跟行动次数有关（有点像求E(x^2)的味道），考虑做两次概率DP。

dp1[x]表示点x到终点n的期望天数，那么dp1[x]=( dp1[x]+sigma(dp1[y]) ) / (du+1) + 1 。(du是x点度数，y是x儿子)。

dp2[x]表示点x到终点n的期望代价，那么dp2[x]=( dp2[x]+dp1[x]+1 + sigma(dp2[y]+dp1[y]+1) ) / (du+1)。(du和y同上)

先求dp1之后求dp2，答案就是dp2[1]。

代码写得很丑：

#include<bits/stdc++.h>

using namespace std;

const int N=2e5+;

int n,m;

vector<int> G[N];

double dp1[N],dp2[N];

void dfs1(int x) {

    if (x==n) return;

    if (dp1[x]!=) return;

    double tmp=;

    for (int i=;i<G[x].size();i++) {

        int y=G[x][i];

        dfs1(y);

        tmp+=dp1[y];

    }

    tmp+=G[x].size()+;

    tmp/=(double)G[x].size();

    dp1[x]=tmp;

}

void dfs2(int x) {

    if (x==n) return;

    if (dp2[x]!=) return;

    double tmp=;

    for (int i=;i<G[x].size();i++) {

        int y=G[x][i];

        dfs2(y);

        tmp+=dp2[y]+dp1[y]+;

    }

    tmp+=dp1[x]+;

    tmp/=(double)G[x].size();

    dp2[x]=tmp;

}

int main()

{

    int T; cin>>T;

    while (T--) {

        scanf("%d%d",&n,&m);

        for (int i=;i<=n;i++) G[i].clear();

        for (int i=;i<=m;i++) {

            int x,y; scanf("%d%d",&x,&y);

            G[x].push_back(y);

        }

        for (int i=;i<=n;i++) dp1[i]=dp2[i]=;

        dfs1();

        dfs2();

        printf("%.2lf\n",dp2[]);

    }

    return ;

}