HDU 5001

http://acm.hdu.edu.cn/showproblem.php?pid=5001

每次去掉要算的点，求出到达其他点的概率，就是不能到达这个点的概率

开始想去算到达这个点的概率，再去减，不过这种方法证实是不对的，重复走的情况会重复计算

#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

#include <algorithm>

#include <vector>

using namespace std ;

double dp[][] ;

int mp[][] ;

int cnt[] ;

int main()

{

    int T ;

    scanf("%d",&T) ;

    while(T--)

    {

        int n,m,d ;

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

        memset(mp,,sizeof(mp)) ;

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

        {

            int a,b ;

            scanf("%d%d",&a,&b) ;

            mp[a][b]=mp[b][a]= ;

        }

        memset(cnt,,sizeof(cnt)) ;

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

        {

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

            {

                if(i==j)continue ;

                if(mp[i][j])cnt[i]++ ;

            }

        }

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

        {

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

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

                    dp[i][j]=0.0 ;

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

                dp[i][]=1.0/n ;

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

            {

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

                {

                    if(v==j)continue ;

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

                    {

                        if(mp[h][j])dp[h][i]+=dp[j][i-]*(1.0/cnt[j]) ;

                    }

                }

            }

            double ans=0.0 ;

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

            {

                if(v==i)continue ;

                ans+=dp[i][d] ;

            }

            printf("%.6lf\n",ans) ;

        }

    }

    return  ;

}