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;

}

记忆化搜索： 每次去掉一个点，然后对剩下的点进行记忆化搜索

#include "stdio.h"

#include "string.h"

#include "vector"

using namespace std;

int vis[101][10011],cnt[101];

double dp[101][10011];

int d;

vector<int>map[101];

double dfs(int a,int b,int c) //当前在a点，已经走了b步，不经过c点

{

    int i;

    double ans;

    if (vis[a][b]) return dp[a][b];

    vis[a][b]=1;

    ans=0;

    if (b>d) return dp[a][b]=1;

    for (i=0;i<map[a].size();i++)

        if (map[a][i]!=c)

            ans+=1.0/cnt[a]*dfs(map[a][i],b+1,c);

    return dp[a][b]=ans;

}

int main()

{

    int Case,n,m,i,a,b;

    scanf("%d",&Case);

    while (Case--)

    {

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

        memset(cnt,0,sizeof(cnt));

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

            map[i].clear();

        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++)

            map[0].push_back(i);

        cnt[0]=n;

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

        {

            memset(vis,0,sizeof(vis));

            printf("%.10lf\n",dfs(0,0,i));

        }

    }

    return 0;

}