传送门

题目大意:给定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)

CF-1025D Recovering BST(区间dp)

传送门 题意:给定n个整数,问是否能生成一棵BST(二分查找树,左子树都比它小,右子树都比它大),并且有边相连的点权的gcd>1。 思路:区间dp,dp[l][...

阅读全文

牛客网暑期多校第五场E room(费用流)

传送门 题意:有n个宿舍,每个宿舍住4个人,给定去年n个宿舍的人员构成,今年n个4人组合的情况,求最少几个人需要搬寝室。 思路:转化为最小费用最大流解...

阅读全文

HDU-4091 Zombie’s Treasure Chest(暴力)

传送门 题意:有一个容量为n的箱子,和无限多的两种珠宝,体积和价值分别是s1,v1,s2,v2,求能装下的最大价值。 思路:直接暴力枚举会TLE,先计算s1 s2的LC...

阅读全文

欢迎留言