P4206 [NOI2005]聪聪与可可(最短路边+记忆化期望)

聪聪与可可

$第一个难题就是聪聪的走位过于离谱$

绞尽脑汁都不知道怎么处理…其实预处理一下就好了呀!!

我们直接枚举聪聪在点$i$,可可在点$j$

从$i$开始跑最短路,然后枚举$i$的相邻点$k$看看$k$是不是最短路上的点

是的话就可以更新,这样就得到了$id[i][j]$表示聪聪下一步走到哪个点

然后又不会做了…

转移具有明显的依赖关系…但是是有终点的

比如当$i==j$时,$dp[i][j]=0$

当$i$和$j$距离不超过$2$,$dp[i][j]=1$

所以我们可以记忆化搜索,这样变得很简单了呢

#include <bits/stdc++.h> using namespace std; struct edge{ int to,nxt; }d[2009]; int head[2009],cnt=1; void add(int u,int v){ d[++cnt]=(edge){v,head[u]},head[u]=cnt; } int n,m,s,t,dis[1009][1009],vis[1009],id[1009][1009],in[1009]; void spfa(int s) { dis[s][s]=0; queue<int>q; q.push(s); while( !q.empty() ) { int u=q.front(); q.pop(); vis[u]=0; for(int i=head[u];i;i=d[i].nxt ) { int v=d[i].to; if( dis[s][v]>dis[s][u]+1 ) { dis[s][v]=dis[s][u]+1; if( !vis[v] ) vis[v]=1,q.push(v); } } } } double dp[1009][1009]; double dfs(int u,int v) { if( dp[u][v] ) return dp[u][v]; if( u==v ) return 0; int q=id[u][v],w=id[q][v]; if( q==v||w==v ) return 1; for(int i=head[v];i;i=d[i].nxt ) { int vv=d[i].to; dp[u][v]+=dfs(w,vv); } dp[u][v]+=dfs(w,v); dp[u][v]=dp[u][v]/(in[v]+1.0)+1.0; } int main() { cin >> n >> m >> s >> t; for(int i=1;i<=m;i++) { int l,r; cin >> l >> r; add(l,r); add(r,l); in[l]++,in[r]++; } memset(dis,20,sizeof(dis)); memset(id,20,sizeof(id)); for(int i=1;i<=n;i++) spfa(i); for(int i=1;i<=n;i++)//聪聪的位置 for(int j=head[i];j;j=d[j].nxt )//相邻点的位置 { int v=d[j].to; for(int q=1;q<=n;q++)//可可的位置 if( dis[i][q]-1==dis[v][q] ) id[i][q]=min( id[i][q],v ); } printf("%.3lf",dfs(s,t) ); }