首页 > 代码库 > HDU 5001 Walk 概率DP
HDU 5001 Walk 概率DP
题目大意：
一个人随即从一个点出发，到达邻接点的概率相同，求出走d步都不会到达1~n点的每一项的不可能概率（这里第一次随即取的点是要求的点也算到达过了）
这道题开始一直在计算到达那一点的可能性，最后用1-ans[i]，但到最后还是没有找到自己哪里错了，有机会再看看
后来直接计算不可能概率，通过dp找到一直走d步后还能到达非自己所要的num的那些点，每次访问到num点，都直接跳过不理它，使其概率不能下传就行了
然后在solve函数中，把所有除num外的dp[j][d]相加就成功了
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <queue> 5 #include <vector> 6 using namespace std; 7 #define N 52 8 vector<int> G[N]; 9 int n,m,d;10 double dp[N][10005],ans[N];11 void bfs(int num)12 {13 memset(dp,0,sizeof(dp));14 for(int i=1;i<=n;i++)15 if(i!=num)16 dp[i][0] = 1.0/n;17 else dp[i][0]=0; //对于已经到达的点不往下继续传值18 19 for(int i=0;i<d;i++){20 for(int j=1;j<=n;j++){21 for(int m=0;m<(int)G[j].size();m++){22 //因为求不到的可能，所以遇到自己需要到达的点就不计算，使其保持空值，无法向下传值23 if(G[j][m]!=num){24 dp[G[j][m]][i+1]+=dp[j][i]*1.0/(int)G[j].size();25 //cout<<dp[j][i]<<endl;26 }27 }28 }29 }30 }31 32 void solve()33 {34 memset(ans,0,sizeof(ans));35 for(int i=1;i<=n;i++){36 bfs(i);37 for(int j=1;j<=n;j++){38 if(j!=i)39 ans[i]+=dp[j][d];40 //将所有能走到最后一步且不是自己所要终点的可能性相加即是不到i的概率41 }42 }43 }44 45 int main()46 {47 int T,a,b;48 scanf("%d",&T);49 while(T--){50 51 scanf("%d%d%d",&n,&m,&d);52 53 for(int i=1;i<=n;i++) G[i].clear();54 55 for(int i=0;i<m;i++){56 scanf("%d%d",&a,&b);57 G[a].push_back(b);58 G[b].push_back(a);59 }60 61 solve();62 63 for(int i=1;i<=n;i++)64 printf("%.10f\n",ans[i]);65 }66 return 0;67 }
HDU 5001 Walk 概率DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。