【dp】hdu5001

タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=5001
人はすぐに1つの点から出発して、隣接する点に着く確率は同じで、d歩を出てすべて1~n点のすべての項に着くことができない確率を求めます
去年のネットの时、最初はある点の概念を直接計算して減らして、それからサンプルが通れないことに気づいて、やっとこのように何度も到着する確率を繰り返し計算することに気づきました...
f[i][j]はiステップがjに到達する確率を表しているが、各点について一度求め、点xについてf[i][j]を求める場合はxを通らないことを保証してから減算すればよい
テニスの試合の時にサンプルを過ぎてwaを1発したのを覚えていて、それから30分以上研究して、それから偶然に-0.0000000を出力したことに気づきました......その涙は満面に流れています......
もう一度やってみるとはっきりした感じがしますorz

#include<iostream>
#include<cstring>
#include<cstdio>
#include<math.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int n, m, d;
double f[10010][60];
bool a[60][60];
int deg[60];
double ans[60];
bool comp(int a, int b)
{
    return a > b;
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%d%d", &n, &m, &d);
        memset(a, 0, sizeof(a));
        memset(f, 0, sizeof(f));
        memset(deg, 0, sizeof(deg));
        for (int i = 1; i <= m; i++)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            a[x][y] = 1;
            a[y][x] = 1;
            deg[x]++;
            deg[y]++;
        }

        for (int i = 1; i <= n; i++)
        {
            ans[i]=1;
            f[0][i] = 1.0 / n;
        }
        for (int k = 1; k <= n; k++)
        {
            for (int step = 1; step <= d; step++)
            {
                for (int i = 1; i <= n; i++)
                {
                    f[step][i] = 0;
                    for (int j = 1; j <= n; j++)
                    {
                        if ((j != k) && (a[j][i] == 1))
                        {
                            f[step][i] +=  (f[step - 1][j] *  (1.0 / (deg[j])));
                            //printf("%d %d %.6lf
 ", i, j, f[step - 1][j] *  (1.0 / deg[j]));
                            //if (f[step][i] > 1.0) f[step][i] = 1.0;
                        }
                    }
                }
            }

            double sum = 1;
            for(int step = 0; step <= d; step++)
            {
                ans[k] -= f[step][k];         
            }
           printf("%.10lf
",fabs(ans[k]));

           for (int i = 1; i <= n; i++)
            {
                f[0][i] = 1.0 / n;
            }
        }

    }
    return 0;
}