题目链接：https://nanti.jisuanke.com/t/41301
题目大意：
给定一个没有循环的有向图，它从节点1开始，到节点n结束。
有一个机器人从1开始，每天都会以相同的概率前往相邻节点之一或静止不动。每天机器人的耐久性消耗量等于经过的天数。
请计算机器人到达节点n时的预期耐久性消耗量。
保证只有一个节点（节点1）的in-degree等于00，并且只有一个节点（节点n）的out-degree等于0.并且图中没有多个边缘。
解题思路：
设dp【i】为从i到达终点n的期望时间那么很容易得到：
接下来设ans【i】为从i到达终点的耐久值消耗量，那么状态转移方程为 ans【u】=ans【u】/(outdeg【u】+1)+1/(outdey【u】+1）*∑ans【v】+dp【u】。由于此图为有向无环图，所以跑边拓扑边转移即可。
#include<bits/stdc++.h> using namespace std; const int maxn=1e5+5; struct st{ int to,next; }stm[maxn*2]; int cnt; int head[maxn]; void add(int u,int v){ stm[cnt].to=v; stm[cnt].next=head[u]; head[u]=cnt++; } int cd[maxn]; int cd1[maxn]; double dp[maxn]; double ans[maxn]; queue<int> que; int main(){ int t; scanf("%d",&t); while(t--){ int n,m; int u,v; memset(head,-1,sizeof(head)); memset(cd,0,sizeof(cd)); memset(dp,0,sizeof(dp)); memset(ans,0,sizeof(ans)); memset(cd1,0,sizeof(cd1)); cnt=0; scanf("%d%d",&n,&m); for(int i=0;i<m;i++){ scanf("%d%d",&u,&v); add(v,u); cd[u]++; cd1[u]++; } while(!que.empty())que.pop(); que.push(n); while(!que.empty()){ int now=que.front(); que.pop(); for(int i=head[now];~i;i=stm[i].next){ int to=stm[i].to; dp[to]+=1.0/(cd[to]+1)*dp[now]; ans[to]+=1.0/(cd[to]+1)*ans[now]; //1.0*(cd[to]+1)/cd[to]; cd1[to]--; if(cd1[to]==0){ dp[to]=(dp[to]+1)*1.0*(cd[to]+1)/cd[to]; ans[to]=(ans[to]+dp[to])*1.0*(cd[to]+1)/cd[to]; que.push(to); } } } printf("%.2lf ",ans[1]); } return 0; }