HDoj 5001 Walk【確率DP】【ステップ数制限で一点を通らない確率を求める】

Walk
Time Limit: 30000/15000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 728    Accepted Submission(s): 455
Special Judge
Problem Description
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.
 
Input
The first line contains an integer T, denoting the number of the test cases.
For each test case, the first line contains 3 integers n, m and d, denoting the number of vertices, the number of edges and the number of steps respectively. Then m lines follows, each containing two integers a and b, denoting there is an edge between node a and node b.
T<=20, n<=50, n-1<=m<=n*(n-1)/2, 1<=d<=10000. There is no self-loops or multiple edges in the graph, and the graph is connected. The nodes are indexed from 1.
 
Output
For each test cases, output n lines, the i-th line containing the desired probability for the i-th node.
Your answer will be accepted if its absolute error doesn't exceed 1e-5.
 
Sample Input

   
   
   
   

    
    
    
    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
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    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
   
   
   
   

 
題意:N個の点とM本の双方向の辺の図をあげて、それぞれの辺は1歩の距離です.現在、任意の起点からk歩(k歩が足りない前に停止することは許されない)を出発することが要求され、中間は1点以上通過することができる.君に要求を満たしていると聞く
の前提でu点を通過しない確率(1<=u <= N).
まず,jステップ目にi点に到達する確率をdp[i][j]で表す.
1つのエッジについて.明らかにdp[a][j]+=dp[b][j-1]*(1/size)がある.(sizeはaに直接エッジが接続されている点の数を表す)
構想:時間制限15000 ms、直接三重循環暴力.
各点u(1<=u<=N)について,uを通過する総確率ans=を求める. (和を求める)dp[u][j](0<=j<=N).1でansを引くとokです.
u点の総確率を求める時、2つの情況に分けて討論します
一:起点はu点で、確率は明らかに1.0/Nである.
二:始点がu点でない場合、u以外のN-1点しか選択できません(ただし、任意の点の確率は1.0/Nです).
第2のケースでは、dp配列を初期化する際に、dp[i][0]=1.0/N(1<=i<=N&&i!=u)があることに注意する.
ACコード:

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
double dp[60][10010];//dp[i][j]   j   i   
vector<int> G[60];
int N, M, step;
void init()
{
    for(int i = 1; i <= N; i++)
        G[i].clear();
}
void getMap()
{
    int x, y;
    while(M--)
    {
        scanf("%d%d", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
}
double getans(int u)
{
    double ans = 0;//  u    
    memset(dp, 0, sizeof(dp));
    for(int i = 1; i <= N; i++)
    {
        if(i == u) continue;
        dp[i][0] = 1.0 / N;//          
    }
    for(int j = 1; j <= step; j++)//      
    {
        for(int i = 1; i <= N; i++)//     
        {
            if(i == u) continue;//    u
            double p = 1.0 / G[i].size();//                
            for(int k = 0; k < G[i].size(); k++)
            {
                int v = G[i][k];
                dp[v][j] += dp[i][j-1] * p;
            }
        }
        ans += dp[u][j];// j   u   
    }
    return 1 - ans - 1.0 / N;
}
void solve()
{
    for(int i = 1; i <= N; i++)
        printf("%.10lf
", getans(i));
}
int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d%d", &N, &M, &step);
        init();
        getMap();
        solve();
    }
    return 0;
}