[NOI2005]聪聪与可可（期望）

题意

OI版猫和老鼠

给定一个有n个点的图（\(n\leq 1000\)），在s点有一只猫，t点有一只jerry，每一单位时间猫先走：沿着到jerry的路径中的最短路走一步，如果同时存在多条最短路则选择走一步后序号更小的一条，另外，如果这一步没有走到jerry所在的点，猫会再走一步（砸瓦鲁多）；jerry后走，可等概率的向直接与自己所在的点走一步或者选择不动（即各个点概率均为1/(入度+1)），求猫抓住jerry的期望时间

思路

在做期望dp之前，要先解决一个问题：猫的走路姿态问题

关于猫走法的一些考察

这道题中猫的走法看似难以捉摸，其实可以看出，对于确定的( s ,t )，猫的着陆点也是确定的，所以是可以预处理出来的

首先，最短路这一个限制说明了是要对每一个点跑一次spfa（2005年spfa尚未狗带），求出dis数组之后，我们还要求出对应的nxt数组，表示从s向t跳一步之后到达的位置（具体的，如何判断一个点是否为s到t最短路上的走一步的点，只要满足dis[s][t]-1==dis[v][t]，那么v就是这样的一个点）

期望dp

预处理上面的nxt数组之后，这道题就是一道比较简单的期望dp了

按照套路，设f[ i ] [ j ]表示猫在i，jerry在j的总期望，ans=f[ s ] [ t ]

初始状态：

s==t时，f[ s ] [ t ]=0
t==nxt[ fir ] [ t ] or t==nxt[ sec ][ t ]时，f [ s ] [ t ]=1
其他情况下，f[ s ] [ t ] =sigma(f[ sec ] [ t ] / ( rd + 1 ) )+1

其中，fir=nxt[ s ] [ t ]，即从s向t走一步，同样，sec=nxt[ fir ] [ t ]，即从s向t走两步

代码采用记忆化搜索完成dp

Code：

#include<bits/stdc++.h>
#define N 1005
#define INF 1000000000
using namespace std;
typedef long double ld;
int n,m,s,t;
int rd[N],nxt[N][N],dis[N][N];
ld f[N][N];
bool vis[N][N];
struct Edge
{
    int next,to;
}edge[N<<2];int head[N],cnt=1;
void add_edge(int from,int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}
template <class T>
void read(T &x)
{
    char c;int sign=1;
    while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;
    while((c=getchar())>='0'&&c<='9') x=(x<<1)+(x<<3)+c-48; x*=sign; 
}
void spfa(int *dis,int s)
{
    bool exist[N]={0};
    queue<int> q;
    q.push(s);dis[s]=0;exist[s]=1;
    while(!q.empty())
    {
        int u=q.front();q.pop();exist[u]=0;
        for(int i=head[u];i;i=edge[i].next)
        {
            int v=edge[i].to;
            if(dis[v]>dis[u]+1)
            {
                dis[v]=dis[u]+1;
                if(!exist[v]) {exist[v]=1; q.push(v);}
            }
        }
    }
    
}
ld dfs(int s,int t)
{
    if(vis[s][t]) return f[s][t];
    if(s==t) return f[s][t]=0;
    int fir=nxt[s][t];
    int sec=nxt[fir][t];
    f[s][t]=1;
    if(fir==t||sec==t) return 1;
    for(int i=head[t];i;i=edge[i].next)
    {
        int v=edge[i].to;
        f[s][t]+=dfs(sec,v)/(rd[t]+1);
    }
    f[s][t]+=dfs(sec,t)/(rd[t]+1);
    vis[s][t]=1;
    return f[s][t];
}
int main()
{
    read(n);read(m);
    read(s);read(t);
    for(int i=1;i<=m;++i)
    {
        int x,y;
        read(x);read(y);
        add_edge(x,y);
        add_edge(y,x);
        rd[x]++;rd[y]++;
    }
    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],i);
    for(int i=1;i<=n;++i)
    for(int j=1;j<=n;++j)
    for(int h=head[i];h;h=edge[h].next)
    {
        int v=edge[h].to;
        if(dis[i][j]-1==dis[v][j]) nxt[i][j]=min(nxt[i][j],v);
    }
    printf("%.3Lf",dfs(s,t));
    return 0;
}

这道题分点讨论比较多，只要把问题拆成许多小问题，就会发现是许多小模板拼凑成的，是一道期望dp入门好题