HDU-5001 Walk （概率dp）

传送门

思路：概率dp，定义dp[u][i][j]：经过了j步之后落在i点且从来不经过u点的概率。最后对于各个点，从不经过它的概率就是dp[u][*][d]的和。

在实际操作过程中，可以把dp数组变成二维的，即变成dp[i][j]。

ans[k]可以考虑成走d步都不经过k点，最后停留点也不是k点的概率之和。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 55;
const double eps = 1e-8;

int n, m, d;
double dp[maxn][10010];
double ans[maxn]; 
vector<int> map[maxn];

int main() {
	int t, x, y;
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d%d", &n, &m, &d);
		for (int i = 1; i <= n; i++)
			map[i].clear();

		for (int i = 1; i <= m; i++) {
			scanf("%d%d", &x, &y);
			map[x].push_back(y);
			map[y].push_back(x);
		}

		for (int k = 1; k <= n; k++) {
			memset(dp, 0, sizeof(dp));
			for (int i = 1; i <= n; i++)
				dp[i][0] = 1.0 / n;
			for (int i = 0; i < d; i++) {
				for (int j = 1; j <= n; j++) {
					if (j == k)
						continue;
					int size = map[j].size();
					for (int l = 0; l < size; l++) {
						int u = map[j][l];
						dp[u][i+1] += dp[j][i] * 1.0 / size;
					}
				}
			}
			ans[k] = 0.0;
			for (int i = 1; i <= n; i++) 
				if (i != k)
					ans[k] += dp[i][d];
			printf("%.10f\n", ans[k]);
		}
	}
	return 0;
}