HDU 5001 Walk

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

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

暴力。dp[d][i]表示走了d步时走到i的概率。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<limits.h>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long LL;
int t,n,m,d;
double dp[10000+10][55];
vector<int>v[55];
void solve(int x)
{
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++)
        dp[0][i]=1.0/n;
    for(int i=0;i<d;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(j==x)  continue;
            for(int k=0;k<v[j].size();k++)
                dp[i+1][v[j][k]]+=dp[i][j]*1.0/v[j].size();
        }
    }
    double ans=0.0;
    for(int i=1;i<=n;i++)
    {
        if(i!=x)
            ans+=dp[d][i];
    }
    printf("%.5f\n",ans);
}
int main()
{
    int x,y;
    scanf("%d",&t);
    while(t--)
    {
        for(int i=0;i<55;i++)
            v[i].clear();
        scanf("%d%d%d",&n,&m,&d);
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&x,&y);
            v[x].push_back(y);
            v[y].push_back(x);
        }
        for(int i=1;i<=n;i++)
            solve(i);
    }
    return 0;
}

另附别人丧心病狂的头文件，我也是醉了

HDU 5001 Walk

原文：http://blog.csdn.net/u013582254/article/details/39259117