概率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

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;

}