题意：
n个点m条边构成无向图。每一步可以从一个点走向与其连接的另一个点。每一步的概率都相同。对于每个点而言，考虑所有步数为d的旅行路线，求不经过它的概率。（不经过该点的路线总数 / 所有路线总线）
数据范围： n<=50, n-1<=m<=n*(n-1)/2, 1<=d<=10000
解法：
dp[i][k]：不经过结点x，第k步到达结点i的概率。初始时dp[i][0] = 1.0 / n （想象开始时从一个虚拟结点走向各点算第0步）
枚举去掉结点，算dp[i][k]之和.
代码：
#include <cstdio> #include <iostream> #include <string.h> #include <cstdlib> #include <algorithm> #include <queue> #include <vector> #include <cmath> #include <map> #include <stack> using namespace std; int const uu[4] = {1,-1,0,0}; int const vv[4] = {0,0,1,-1}; typedef long long ll; int const maxn = 50005; int const inf = 0x3f3f3f3f; ll const INF = 0x7fffffffffffffffll; double eps = 1e-10; double pi = acos(-1.0); #define rep(i,s,n) for(int i=(s);i<=(n);++i) #define rep2(i,s,n) for(int i=(s);i>=(n);--i) #define mem(v,n) memset(v,(n),sizeof(v)) #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 int T,n,m,d; vector<int> graph[55]; double dp[55][10005]; //node x cost k steps void dpCalc(int x){ //remove node x mem(dp,0.0); rep(i,1,n){ if(i!=x) dp[i][0] = 1.0/n; else dp[i][0] = 0.0; } rep(k,0,d-1) rep(i,1,n){ if(i!=x){ int L = graph[i].size(); rep(j,0,L-1) dp[graph[i][j]][k+1] += (dp[i][k]/L); } } double ans = 0.0; rep(i,1,n){ if(i!=x) ans += dp[i][d]; } printf("%.10lf ",ans); } int main(){ cin >> T; while(T--){ scanf("%d%d%d",&n,&m,&d); rep(i,1,n) graph[i].clear(); while(m--){ int a,b; scanf("%d%d",&a,&b); graph[a].push_back(b); graph[b].push_back(a); } rep(i,1,n){ dpCalc(i); } } }