\(\\\)
一张\(N\)个点，\(M\)条边的有向图中，猫在\(A\)点，鼠在\(B\)点，每一秒两者按照以下规则移动：
- 猫先走去往老鼠所在地的最短路，可以走一步或两步，多条路径的话走点编号最小的。
- 鼠等概率移动到直接连通的一个点或不动（概率为\(\frac{1}{deg_v+1}\)）。
当任意时刻猫到达鼠所在地时鼠被吃掉，求鼠被吃掉的期望时间。
- \(N,M\in [0,10^3]\)
\(\\\)
\(Solution\)
BZOJ200题达成纪念
注意到图非常稀疏，可以\(SPFA\)预处理出，对于任意点对\((x,y)\)，\(x\)按规则走向\(y\)的第一步去往的点\(next[x][y]\)。
具体操作是现对每个点跑一遍\(SPFA\)，设\(dis[u][v]\)表示从\(u\)到\(v\)的最短路长度，则所找的点的编号\(next[x][y]=min\{v|dis[v][y]+1=dis[x][y]\}\)。那么对于每一个要处理的猫和鼠的地点\((A,B)\)，猫下一步到达的点就是\(next[next[A][B]][B]\)。
注意到猫每一秒都会向靠近鼠的方向移动两步，而鼠每一秒会向不确定的方向移动一步，所以鼠是一定会被吃掉的，不妨暴力\(dfs\)下去找到猫捉到鼠的时间。而搜索状态量过多，所以需要记忆化。设\(f[i][j]\)表示猫在\(i\)号节点，鼠在\(j\)号节点时时间的期望，那么初始化就是\(f[i][i]=0,f[i][j]=1\big|dis[i][j]\le 2,i\not=j\)。
然后记搜就可以了，转移方程很好理解，就是猫走向该走的地方，鼠下一步枚举，没搜过就搜一下：
\[ f[i][j]=\frac{\sum_{dis[j][v]=1}f\big[next[next[i][j]][j]\big]\big[v\big]\ +\ f\big[next[next[i][j]][j]\big]\big[j\big]}{deg[j]+1}+1 \]
\(\\\)
\(Code\)
#include#include #include #include #include #include #include #include #define N 1010#define R register#define gc getchar#define inf 2000000000using namespace std;inline int rd(){ int x=0; bool f=0; char c=gc(); while(!isdigit(c)){if(c=='-')f=1;c=gc();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();} return f?-x:x;}bool vis[N];double f[N][N];int n,m,s,t,tot,hd[N],d[N][N],deg[N],nxt[N][N];struct edge{int to,nxt;} e[N<<1];inline void add(int u,int v){ e[++tot].to=v; e[tot].nxt=hd[u]; hd[u]=tot;}queue q;inline void bfs(int x){ q.push(x); d[x][x]=0; while(!q.empty()){ int u=q.front(); q.pop(); vis[u]=0; for(R int i=hd[u],v;i;i=e[i].nxt) if(d[x][v=e[i].to]>d[x][u]+1){ d[x][v=e[i].to]=d[x][u]+1; if(!vis[v]) vis[v]=1,q.push(v); } }}inline void dfs(int u,int v){ double res=0.0; int nu=nxt[nxt[u][v]][v]; for(R int i=hd[v],nv;i;i=e[i].nxt){ if(f[nu][nv=e[i].to]<-10) dfs(nu,nv); res+=f[nu][nv]; } if(f[nu][v]<-10) dfs(nu,v); f[u][v]=(res+f[nu][v])/(deg[v]+1)+1;}int main(){ n=rd(); m=rd(); s=rd(); t=rd(); for(R int i=1,u,v;i<=m;++i){ u=rd(); v=rd(); add(u,v); add(v,u); } for(R int i=1;i<=n;++i) for(R int j=1;j<=n;++j) d[i][j]=nxt[i][j]=inf,f[i][j]=-(double)inf; for(R int i=1;i<=n;++i) bfs(i); for(R int i=1;i<=n;++i) for(R int j=1;j<=n;++j) if(d[i][j]