I used to think I could be anything, but now I know that I couldn't do anything. So I started traveling.

The nation looks like a connected bidirectional graph, and I am randomly walking on it. It means when I am at node i, I will travel to an adjacent node with the same probability in the next step. I will pick up the start node randomly (each node in the graph has the same probability.), and travel for d steps, noting that I may go through some nodes multiple times.

If I miss some sights at a node, it will make me unhappy. So I wonder for each node, what is the probability that my path doesn't contain it.

2

5 10 100

1 2

2 3

3 4

4 5

1 5

2 4

3 5

2 5

1 4

1 3

10 10 10

1 2

2 3

3 4

4 5

5 6

6 7

7 8

8 9

9 10

4 9

0.0000000000

0.0000000000

0.0000000000

0.0000000000

0.0000000000

0.6993317967

0.5864284952

0.4440860821

0.2275896991

0.4294074591

0.4851048742

0.4896018842

0.4525044250

0.3406567483

0.6421630037

第一道比赛出的概率dp。找好状态记忆化搜索即可。

#include<bits/stdc++.h>

#define MAX 55

using namespace std;

typedef long long ll;

int n,m,k;

double ans;

double dp[MAX][];

vector<int> v[MAX];

double dfs(int f,int x,int s){

    int i;

    if(s>=k) return ;

    if(dp[x][s]>-) return dp[x][s];

    int xx=v[x].size();

    double cnt=;

    for(i=;i<v[x].size();i++){

        if(v[x][i]==f) continue;

        cnt+=dfs(f,v[x][i],s+)*(1.0/xx);

    }

    dp[x][s]=cnt;

    return cnt;

}

int main()

{

    int t,i,j;

    int x,y;

    scanf("%d",&t);

    while(t--){

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

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

            v[i].clear();

        }

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

            scanf("%d%d",&x,&y);

            v[x].push_back(y);

            v[y].push_back(x);

        }

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

            ans=;

            memset(dp,-,sizeof(dp));

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

                if(i==j) continue;

                ans+=dfs(i,j,)*(1.0/n);

            }

            printf("%.10f\n",ans);

        }

    }

    return ;

}