HDU 5001 Walk

时间:2021-01-01 15:58:12

解题思路:这是一道简单的概率dp,只要处理好相关的细节就可以了。

    dp[d][i]表示走d步时走到i的改概率,具体参考代码:

 #include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
const int N = ;
const int M = ;
double dp[N][M];
int n, m, t, d;
vector<int> v[M]; //vector表示不定长数组 double solve(int x)
{
double ans = ;
memset(dp, , sizeof(dp));
for(int i = ; i <= n; i++) dp[][i] = 1.0/n;// 表示还没走时,走到每个点的概率
for(int i = ; i < d; i++)
{
for(int j = ; j <= n; j++)
{
if(j == x) continue; //不会走到与自己相同的点上
int s = v[j].size(); //与点j相连的数有多少个
for(int k = ; k < s; k++)
{
int c = v[j][k]; //与j相连的第k个数
dp[i+][c] += dp[i][j]*1.0/s; //这里很难给你讲清楚,自己好好思考
//心中有个具体的场景就更好
}
}
}
for(int i = ; i <= n; i++)
{
if(i == x) continue;
ans += dp[d][i]; //第d步到其它所有点的概率之和为
//第d步没走到第x点的概率。
}
return ans;
} int main()
{
int a, b;
scanf("%d", &t);
while(t--)
{
scanf("%d %d %d", &n, &m, &d);
for(int i = ; i <= n; i++) v[i].clear();
while(m--)
{
scanf("%d %d", &a, &b);
v[a].push_back(b); //向尾部添加元素,关于vector的用法,自己参考资料
v[b].push_back(a);
}
for(int i = ; i <= n; i++) printf("%.10lf\n", solve(i));
}
return ;
}