2014 ACM/ICPC Asia Regional Anshan Online

给N个点，M条边组成的图，每一步可以从一个点走到相邻任一点，概率相同，问D步后没走到过每个点的概率

概率DP  测试数据太水了。。。。10000*50*50*50都能过

加个vector优化到

#include "stdio.h"
#include "string.h"
#include "vector"
using namespace std;

double dp[10][101][101];
double ans[101];
vector<int>map[101];
int cnt[101];
int main()
{
    int n,m,d,Case,a,b,i,j,k,l;
    scanf("%d",&Case);
    while (Case--)
    {
        scanf("%d%d%d",&n,&m,&d);
        memset(cnt,0,sizeof(cnt));
        while (m--)
        {
            scanf("%d%d",&a,&b);
            cnt[a]++;
            cnt[b]++;
            map[a].push_back(b);
            map[b].push_back(a);
        }
        memset(dp,0,sizeof(dp));

        for (i=1;i<=n;i++)
            for (j=1;j<=n;j++)
            if (i!=j)
            dp[0][i][j]+=1.0/n;  // dp[d][i][j] 第d步，终点为i，中途不经过j的概率

        for (i=1;i<=d;i++)
        {
            memset(dp[i%2],0,sizeof(dp[i%2]));
            for (j=1;j<=n;j++)
                for (k=0;k<map[j].size();k++)
                    for (l=1;l<=n;l++)
                    if (j!=l && j!=map[j][k])
                        dp[i%2][map[j][k]][l]+=dp[1-i%2][j][l]*1.0/cnt[j];
        }
        memset(ans,0,sizeof(ans));
        for (i=1;i<=n;i++)
            for (j=1;j<=n;j++)
                if (i!=j)
            ans[i]+=dp[d%2][j][i];
        for (i=1;i<=n;i++)
        {
            printf("%.10lf\n",ans[i]);
            map[i].clear();
        }
    }
    return 0;
}

HDU 5001 概率DP