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

    科技2022-07-17  135

    聪聪与可可

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

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

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

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

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

    然后又不会做了…

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

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

    i i i j j j距离不超过 2 2 2, d p [ i ] [ j ] = 1 dp[i][j]=1 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) ); }
    Processed: 0.009, SQL: 8