bf bf film bf rajwap.biz tamil pussy fingering desi pron video coxhamster.mobi sexy girl video open xvideoimage pornfactory.info bihari sexy video download سكس كلاسيك مترجم pornclassic.info سكس عراقي hindixxvidio porno-zona.com dise murga indian old women nude rajwap.biz srxyvidio www sexy videoes com indiansexmms.me sxsi bf مصريات شراميط pornvuku.net نيك احلي كس malligi hotel donfreeporn.mobi bengalixxxvideo tsmil sex youjizz.sex perfect girl xxx hd any porn porntubemovs.info xxx thumbzilla نيك طيز مترجم 3gpjizz.info سكس فى السجن xossip bengali kamporn.mobi indian sex play forced indian sex video indiansexgate.mobi sleeping girl xnxx classic video com 2beeg.me indiangirlssexvideos

传送门

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

阅读全文

欢迎留言