题目链接:hdu 5001 Walk
题目大意:给定一张图,每次随机移动到下一个节点,问所走完d步后,每个点没有被走过的概率。
解题思路:枚举每节点x,dp[i][j]表示第i步走到j节点的概率(没有经过x)。
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 55;
const int maxm = 10005;
int N, M, D;
vector<int> g[maxn];
double dp[maxm][maxn];
void init () {
scanf("%d%d%d", &N, &M, &D);
for (int i = 0; i <= N; i++)
g[i].clear();
int x, y;
for (int i = 0; i < M; i++) {
scanf("%d%d", &x, &y);
g[x].push_back(y);
g[y].push_back(x);
}
for (int i = 1; i <= N; i++)
g[0].push_back(i);
}
double solve (int u) {
double ret = 0;
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for (int i = 0; i <= D; i++) {
for (int j = 0; j <= N; j++) {
if (u == j)
continue;
double p = 1.0 / g[j].size();
for (int k = 0; k < g[j].size(); k++)
dp[i+1][g[j][k]] += dp[i][j] * p;
}
ret += dp[i+1][u];
}
return 1.0 - ret;
}
int main () {
int cas;
scanf("%d", &cas);
while (cas--) {
init();
for (int i = 1; i <= N; i++)
printf("%.10lf\n", solve(i));
}
return 0;
}
分享到:
相关推荐
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
各种小数化分数的算法,acm的同学都喜欢看,仅供参考!
hdu 1574 passed sorce
搜索 dfs 解题代码 hdu1241
HDU的一题........HDU DP动态规
hdu2101AC代码
杭州电子科技大学oj平台上的第1010题,是关于搜索的题目,很不错的题
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu 1166线段树代码
自己做的HDU ACM已经AC的题目
HDU最全ac代码
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu动态规划算法集锦
hdu题目分类
HDU图论题目分类