概率DP——题解 P4206 【[NOI2005]聪聪与可可 】

FREEH · 2018-08-15 19:52:35 · 题解

【题目】

【解题思路】

• 分析题目，找出一些细节：
  • 猫可以走一步或两步；
  • 老鼠可以不动；
  • 猫必须走到离老鼠最近的点，如距离有相同，则选编号最小的点。
• 预处理：
  • 由于猫的走位过于神奇，无论使用什么算法都会很麻烦，因此只好进行预处理。预处理出猫在点i，老鼠在点j，猫的下一个走位nxt[i][j]。
  • 然而需要预处理出这个就还需要使用SPFA预处理出猫在点i到达所有点最短路径dis[i][j]，接下来才能预处理出猫的走位。
• 考虑使用概率DP，用f[i][j]表示猫在点i，老鼠在点j，猫抓到老鼠的期望步数是多少。
• 对于f[i][j]，我们进行分类讨论：
  • 如果猫和老鼠同点，即i=j，则f[i][j]=0；
  • 如果猫走一步或两步可以到达j，f[i][j]=1；
  • 否则f[i][j]=sum(f[sec][k]/(p[j]+1))+1（其中，sec表示猫走两步所到达的位置（因为走两步只算一次费用），k表示老鼠可到达的位置（含原地），p[j]表示点j的出度数（即不包含原地））。
• 这个过程可以使用记忆化搜索完成。
• 最终答案是f[s][t]。

【参考程序】

#include<cstdio>
#include<queue>
#include<cstring>
#include<iostream>
using namespace std;
int cur,n,m,s,t;
int head[1005],p[1005];
int dis[1005][1005],nxt[1005][1005];
bool vis[1005],visit[1005][1005];
double f[1005][1005];
struct EDGE{
    int t,next;
}e[2005];
#define INF 0x3f3f3f3f

void add(int a,int b)
{
    cur++;
    e[cur].t=b;
    e[cur].next=head[a];
    head[a]=cur;
}

queue < int > q;
void SPFA(int *dis,int *nxt,int s)
{
    dis[s]=0;
    q.push(s);
    while (!q.empty())
    {
        int u=q.front();q.pop();
        vis[u]=false;
        for (int h=head[u];h!=-1;h=e[h].next)
        {
            int v=e[h].t;
            if (dis[u]+1<dis[v])
            {
                dis[v]=dis[u]+1;
                if (!vis[v])
                {
                    vis[v]=true;
                    q.push(v);
                }
            }
        }
    }
}
double DFS(int u,int v)
{
    if (visit[u][v]) return f[u][v];
    if (u==v) return 0;
    int fir=nxt[u][v];
    int sec=nxt[fir][v];
    if (fir==v||sec==v) return 1;
    f[u][v]=1;
    for (int h=head[v];h!=-1;h=e[h].next)
    {
        int w=e[h].t;
        f[u][v]+=DFS(sec,w)/(p[v]+1);
    }
    f[u][v]+=DFS(sec,v)/(p[v]+1);
    visit[u][v]=true;
    return f[u][v];
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&s,&t);
    memset(head,-1,sizeof head);
    for (int i=1;i<=m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        add(b,a);
        p[a]++;p[b]++;
    }
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
            dis[i][j]=nxt[i][j]=INF;
    }
    for (int i=1;i<=n;i++)
    {
        SPFA(dis[i],nxt[i],i);
    }
    for (int i=1;i<=n;i++)
        for (int h=head[i];h!=-1;h=e[h].next)
        {
            int t=e[h].t;
            for (int j=1;j<=n;j++)
                if (dis[i][j]-1==dis[t][j])
                {
                    nxt[i][j]=min(nxt[i][j],t);
                }
        }
    /*for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
            printf("%d ", nxt[i][j]);
        printf("\n");
    }*/
    printf("%.3lf",DFS(s,t));
    return 0;
}