[概率dp] hdu 5001 Walk

[概率dp] hdu 5001 Walk

題意：n個點(1~n)，m條邊，走k次，雙向邊，每次隨機走一條路，起點也隨機，問不走到各個點的概率是多少。

思路：

概率dp[i][j][k] 前i步 走到j 走不到k的概率。

那麼狀態轉移就是 j能走到的點，傳遞所有dp[i][j][k]的值乘上概率。

代碼：

#include"cstdlib"
#include"cstdio"
#include"cstring"
#include"cmath"
#include"stack"
#include"algorithm"
#include"iostream"
#include"vector"
using namespace std;
#define N 300000
double dp[3][55][55];  //因為內存問題 用滾動數組
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,m,d;
        scanf("%d%d%d",&n,&m,&d);
        vectoredge[55];
        while(m--)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            edge[a].push_back(b);
            edge[b].push_back(a);
        }
        memset(dp,0,sizeof(dp));
        int i,j,k,l;
        for(i=1; i<=n; i++)
        {
            for(j=1; j<=n; j++)
            {
                if(j!=i) dp[0][i][j]+=1.0/n;  //初始化，就是因為起點在i所以走不到j的概率都是n分之1
            }
        }
        for(i=1; i<=d; i++)
        {
            memset(dp[i%2],0,sizeof(dp[i%2]));
            for(j=1; j<=n; j++)
            {
                for(k=0; k<(int)edge[j].size(); k++)
                {
                    for(l=1; l<=n; l++)
                    {
                        if(j!=l&&j!=edge[j][k]) dp[i%2][edge[j][k]][l]+=dp[1-i%2][j][l]*1.0/edge[j].size();
                    }
                }
            }
        }
        double ans[55];
        memset(ans,0,sizeof(ans));
        for(i=1; i<=n; i++)
        {
            for(j=1; j<=n; j++)
                if(i!=j) ans[i]+=dp[d%2][j][i];
        }
        for(i=1; i<=n; i++)
            printf("%.10f\n",ans[i]);
    }
    return 0;
}