题意:
给出一张图;
n个点,m条边,然后走d步;
问走d步不经过第i个点的概率(输出n行,每个点算一次)
思路:
dp[i][j]代表走d步到达j点的概率;
我们可以知道dp[0][j] = 1.0 / n (还没走,以每个点为起点的概率是一样的);
然后我们还可以知道dp[i][j] = dp[i - 1][v[j][k]] / v[j].size(); 就是第i步到j,等于第i-1步到j的临边的概率并除以临边的数量的叠加;
在所有过程中我们要除掉我们所要求的点;
那么dp[d][1] + dp[d][2] ......就是经过ｄ步到达所有点的概率加起来（全都不包括我要求的点），就得到所有不经过该点的概率了；
ＡＣ代码：
#include#include #include #include using namespace std; const int N = 55; int n,m,d; double dp[10005][N]; vector v[N]; void solve(int x) { for(int i = 1; i <= d; i++) { for(int j = 1; j <= n; j++) { if(j == x) continue; for(int k = 0; k < v[j].size(); k++) { if(v[j][k] != x) dp[i][j] += (dp[i - 1][v[j][k]])/v[j].size(); } } } double ret = 0; for(int i = 1; i <= n; i++) { if(i != x) ret += dp[d][i]; } printf("%.10lf\n",ret); } int main() { int t; scanf("%d",&t); while(t--) { for(int i = 0; i <= n; i++) { v[i].clear(); } scanf("%d%d%d",&n,&m,&d); int x,y; for(int i = 1; i <= m; i++){ scanf("%d%d",&x,&y); v[x].push_back(y); v[y].push_back(x); } for(int i = 1; i <= n ;i++) { memset(dp, 0, sizeof(dp)); for(int j = 0; j <= n; j++) { dp[0][j] = 1.0 / (double)n; } solve(i); } } }