cogs 943. [東方S3] 铃仙•优昙华院•稻叶

二次联通门 : cogs 943. [東方S3] 铃仙•优昙华院•稻叶

/*

    cogs 943. [東方S3] 铃仙·优昙华院·稻叶

    概率dp

    貌似做麻烦了

    邻接矩阵和链式前向星都用上了。。。

    dp[pos][i][j]表示 第i秒 在i点 上一个经过的点是j

    方程:

    dp[pos][i][j]=Σdp[pos-1][j][k]*(__out[j]+1-(map[j][k]==1))+dp[pos-1][i][j]*(__out[i]+1-(map[i][j]==1)

    前面的求和考虑的是上一秒从其他的一个节点走过来

    后面的考虑的是上一秒选择停留在原地

    复杂度O(T * N^3)

*/

#include <cstdio>

void read (int &now)

{

    register char word = getchar ();

    for (now = ; word < '' || word > ''; word = getchar ());

    for (; word >= '' && word <= ''; now = now *  + word - '', word = getchar ());

}

#define Max 55

bool map[Max][Max];

int __out[Max * ];

double dp[Max * ][Max][Max];

int __next[Max * ];

int __to[Max * ];

int edge_list[Max * ];

int Edge_Count ;

inline void AddEdge (int from, int to)

{

    Edge_Count ++;

    __next[Edge_Count] = edge_list[from];

    __to[Edge_Count] = to;

    edge_list[from] = Edge_Count;

}

int main (int argc, char *argv[])

{

    freopen ("reisen.in", "r", stdin);

    freopen ("reisen.out", "w", stdout);

    int N, M, T;

    read (N);

    read (M);

    read (T);

    int x, y;

    for (register int i = ; i <= M; i ++)

    {

        read (x);

        read (y);

        map[x][y] = true;

        __out[x] ++;

        AddEdge (x, y);

    }

    dp[][][] = 1.00;

    register bool flag;

    for (register int pos = , i, j, Flan; pos <= T; pos ++)

        for (i = ; i <= N; i ++)

            for (j = ; j <= N; j ++)

                if (dp[pos][i][j] > 0.00)

                {

                    flag = false;

                    if (map[i][j])

                        flag = true;

                    for (Flan = edge_list[i]; Flan; Flan = __next[Flan])

                    {

                        if (__to[Flan] == j)

                            continue;

                        dp[pos + ][__to[Flan]][i] += dp[pos][i][j] * 1.00 / (double)(__out[i] + !flag);

                    }

                    dp[pos + ][i][j] += dp[pos][i][j] * 1.00 / (double)(__out[i] + !flag);

                }

    register double Answer;

    for (register int i = , j; i <= N; i ++)

    {

        Answer = 0.00;

        for (j = ; j <= N; j ++)

            Answer += dp[T][i][j];

        printf ("%.3lf\n", Answer * );

    }

    return ;

}