题意
OI版猫和老鼠
给定一个有n个点的图（(nleq 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 ]
初始状态：
st时，f[ s ] [ t ]=0
tnxt[ 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入门好题