5-05 625 views
题目大意:给定n个点m条边的无向图,每个点作为初始位置的概率相同,在每个点时走向相连每个点的概率相同。一共走d步,问从不经过每个点的概率。
思路:概率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; }
Latest posts by 青鸟千秋 (see all)
- Ceph客户端缓存一致性分析 - 2019年6月21日
- CephFS:什么是CAPS? - 2019年6月21日
- Ceph集群快速搭建教程 - 2019年6月20日