概率DP
dp[j][d] 表示不经过i点走d步到j的概率, dp[j][d]=sigma ( dp[k][d-1] * Probability )
ans = sigma ( dp[j][D] )
Walk
Time Limit: 30000/15000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 401 Accepted Submission(s): 261
Special Judge
The nation looks like a connected bidirectional graph, and I am randomly walking on it. It means when I am at node i, I will travel to an adjacent node with the same probability in the next step. I will pick up the start node randomly (each node in the graph
has the same probability.), and travel for d steps, noting that I may go through some nodes multiple times.
If I miss some sights at a node, it will make me unhappy. So I wonder for each node, what is the probability that my path doesn't contain it.
For each test case, the first line contains 3 integers n, m and d, denoting the number of vertices, the number of edges and the number of steps respectively. Then m lines follows, each containing two integers a and b, denoting there is an edge between node
a and node b.
T<=20, n<=50, n-1<=m<=n*(n-1)/2, 1<=d<=10000. There is no self-loops or multiple edges in the graph, and the graph is connected. The nodes are indexed from 1.
Your answer will be accepted if its absolute error doesn't exceed 1e-5.
2 5 10 100 1 2 2 3 3 4 4 5 1 5 2 4 3 5 2 5 1 4 1 3 10 10 10 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 4 9
0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.0000000000 0.6993317967 0.5864284952 0.4440860821 0.2275896991 0.4294074591 0.4851048742 0.4896018842 0.4525044250 0.3406567483 0.6421630037
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=10010;
int n,m,D;
vector<int> g[maxn];
double dp[55][maxn];
int main()
{
int T_T;
scanf("%d",&T_T);
while(T_T--)
{
scanf("%d%d%d",&n,&m,&D);
for(int i=0;i<=n+1;i++) g[i].clear();
while(m--)
{
int a,b;
scanf("%d%d",&a,&b);
g[a].push_back(b);
g[b].push_back(a);
}
for(int i=1;i<=n;i++)
{
memset(dp,0,sizeof(dp));
for(int j=1;j<=n;j++)
{
if(i!=j) dp[j][0]=1.0/n;
}
for(int d=1;d<=D;d++)
{
for(int j=1;j<=n;j++)
{
if(j==i) continue;
for(int k=0,sz=g[j].size();k<sz;k++)
{
int v=g[j][k];
if(v!=i) dp[j][d]+=dp[v][d-1]*(1./g[v].size());
}
}
}
double ans=0.0;
for(int j=1;j<=n;j++)
{
if(i!=j) ans+=dp[j][D];
}
printf("%.10lf\n",ans);
}
}
return 0;
}