hdu5001 Walk 概率dp

时间：2015-07-22 16:13:29 阅读：148 评论：0 收藏：0 [点我收藏+]

//给一个无向图， n个节点，m条边
//每个节点为起点的概率相同
//问每个节点走d步后不经过这个节点的概率
//不经过这个节点的概率等于去掉该节点的图中走了d步到其他节点的和
//dp[i][j] 为走了i步到达j个节点的概率
//dp[i][j] = segma(dp[i-1][v])/vec[j].size()
#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
using namespace std ;
const int maxm = 10010 ;
const int maxn = 60 ;
double dp[maxm][maxn] ;
double outdegree[maxn] ;
double p[maxn] ;
vector<int>vec[maxn] ;
int main()
{
// freopen("in.txt" ,"r" , stdin) ;
int T ;
int m , n, d ;
scanf("%d" ,&T) ;
while(T--)
{
scanf("%d%d%d" ,&n , &m , &d) ;
memset(p , 0 , sizeof(p)) ;
for(int i = 1;i <= n;i++)
vec[i].clear() ;
for(int i = 1;i <= m;i++)
{
int a , b ;
scanf("%d%d" ,&a ,&b) ;
vec[a].push_back(b) ;
vec[b].push_back(a) ;
}
for(int s = 1;s <= n;s++)
{
memset(dp , 0 , sizeof(dp)) ;
for(int i = 1;i <= n;i++)
dp[0][i] = 1.0/(double)n ;
double ans = 0 ;
for(int i = 1;i <= d;i++)
for(int j = 1;j <= n;j++)
{
if(j == s)continue ;
for(int k = 0;k < vec[j].size() ;k++)
{
int v = vec[j][k] ;
if(v == s)continue ;
dp[i][j] += dp[i-1][v]/(double)vec[j].size();
}
}
dp[0][s] = 1.0/(double)n ;
for(int j = 1;j <= n;j++)
p[s] += dp[d][j] ;
}
for(int i = 1;i <= n;i++)
printf("%lf\n" , p[i]) ;
}
return 0 ;
}

hdu5001 Walk 概率dp

原文：http://blog.csdn.net/cq_pf/article/details/47003567

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)