hdu5001（概率dp）

时间：2022-05-07 21:13:01

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=5001

题意：一个人随即从一个点出发，到达邻接点的概率相同，求出走d步都不会到达1~n点的每一点i的概率。

分析：每次删掉i点去计算d步后到达其他点的概率，加起来的都是没有到达i点的概率。

一开始算出x步到达每点的概率，然后d步后（1-dp[x][i]）^d，错了，因为算每点到达的概率时已经算了到达i点时的概率了。

网络赛时这道水题做不出，好殇。。。。。

#include <cstdio>

#include <cstring>

#include <string>

#include <cmath>

#include <iostream>

#include <algorithm>

#include <queue>

#include <cstdlib>

#include <stack>

#include <vector>

#include <set>

#include <map>

#define LL long long

#define mod 100000000

#define inf 0x3f3f3f3f

#define eps 1e-9

#define N 100010

#define FILL(a,b) (memset(a,b,sizeof(a)))

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

using namespace std;

double dp[][];

vector<int>g[];

int main()

{

    int t,n,m,d;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d%d%d",&n,&m,&d);

        for(int i=;i<=n;i++)g[i].clear();

        for(int i=;i<=m;i++)

        {

            int u,v;

            scanf("%d%d",&u,&v);

            g[u].push_back(v);

            g[v].push_back(u);

        }

        for(int i=;i<=n;i++)

        {

            FILL(dp,);

            for(int j=;j<=n;j++)

                if(j!=i)dp[][j]=1.0/n;

            for(int x=;x<=d;x++)

            {

                for(int j=;j<=n;j++)

                {

                    if(i==j)continue;

                    for(int k=,sz=g[j].size();k<sz;k++)

                    {

                        int v=g[j][k];

                        if(v!=i)dp[x][v]+=dp[x-][j]/sz;

                    }

                }

            }

            double res=;

            for(int j=;j<=n;j++)

                if(i!=j)res+=dp[d][j];

            printf("%.10lf\n",res);

        }

    }

}

相关文章