首页 > 代码库 > HDU 5001

HDU 5001

2024-07-22 11:43:30   216人阅读

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[55][10005] ;int mp[55][55] ;int cnt[55] ;int main(){    int T ;    scanf("%d",&T) ;    while(T--)    {        int n,m,d ;        scanf("%d%d%d",&n,&m,&d) ;        memset(mp,0,sizeof(mp)) ;        for(int i=0 ;i<m ;i++)        {            int a,b ;            scanf("%d%d",&a,&b) ;            mp[a][b]=mp[b][a]=1 ;        }        memset(cnt,0,sizeof(cnt)) ;        for(int i=1 ;i<=n ;i++)        {            for(int j=1 ;j<=n ;j++)            {                if(i==j)continue ;                if(mp[i][j])cnt[i]++ ;            }        }        for(int v=1 ;v<=n ;v++)        {            for(int i=0 ;i<55 ;i++)                for(int j=0 ;j<10005 ;j++)                    dp[i][j]=0.0 ;            for(int i=1 ;i<=n ;i++)                dp[i][0]=1.0/n ;            for(int i=1 ;i<=d ;i++)            {                for(int j=1 ;j<=n ;j++)                {                    if(v==j)continue ;                    for(int h=1 ;h<=n ;h++)                    {                        if(mp[h][j])dp[h][i]+=dp[j][i-1]*(1.0/cnt[j]) ;                    }                }            }            double ans=0.0 ;            for(int i=1 ;i<=n ;i++)            {                if(v==i)continue ;                ans+=dp[i][d] ;            }            printf("%.6lf\n",ans) ;        }    }    return 0 ;}
View Code

 

HDU 5001


联系
我们