?
应该算是一道简单的概率题。想了两个多小时，结果越想越麻烦。开了一个三维数组，MLE了。。
最后借鉴实验室学长的思路，发现这样想很直观，正退就可以。
设dp[j][d]表示不能经过i点走了d步到达j点的概率。那么dp[j][d] = ∑ dp[k][d-1]/edge[k].size()。那么不经过i点的概率为∑dp[j][D]。
#include #include #include #include #include #include #include #include #include #include #include #include #include //#define LL __int64 #define LL long long #define eps 1e-9 #define PI acos(-1.0) using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 55; vector edge[55]; double dp[55][10010]; int n,m,D; int main() { int test,u,v; scanf(%d,&test); while(test--) { scanf(%d %d %d,&n,&m,&D); D++; for(int i = 1; i <= n; i++) edge[i].clear(); for(int i = 1; i <= m; i++) { scanf(%d %d,&u,&v); edge[u].push_back(v); edge[v].push_back(u); } for(int i = 1; i <= n; i++) { memset(dp,0,sizeof(dp)); for(int d = 1; d <= D; d++) { if(d == 1) { for(int j = 1; j <= n; j++) { if(j != i) dp[j][d] = 1.0/n; } } else { for(int j = 1; j <= n; j++) { if(j != i) { for(int g = 0; g < (int)edge[j].size(); g++) { int k = edge[j][g]; if(k != i) dp[j][d] += dp[k][d-1]*1.0/edge[k].size(); } } } } } double ans = 0; for(int j = 1; j <= n; j++) { if(j != i) ans += dp[j][D]; } printf(%.10lf ,ans); } } return 0; }