题解 P4745 【[CERC2017]Gambling Guide】

## 分析 按照期望题一般的做法，我们设 $f[u]$ 为从 $u$ 走到终点 $n$ 的期望花费 设 $du[u]$ 为节点 $u$ 的出度 那么 $f[u]= \frac{\sum_{u->v} min(f[u],f[v])}{du[u]}+1$ 我们会发现这个式子既包含 $f[u]$ 本身又包含与 $f[u]$ 相邻的点 $f[v]$ 不好直接转移 但是我们可以确定，如果 $f[v]<f[u]$ ，那么 $f[v]$ 一定会对 $f[u]$ 做出贡献 因此，我们可以利用 $Dij$ 的思想开一个小根堆，每次取出最小的来更新其它的 因为当前的值是最小的，所以一定不会有其它的点可以影响它 我们设 $u$ 被与它相邻的点的 $f$ 值更新了 $cnt$ 次，这些值的和为 $sum$ 则 $f[u]=\frac{sum+(du[u]-cnt[u]) \times f[u]}{du[u]}+1$ 整理可得 $f[u]=\frac{sum+du[u]}{cnt}$ ## 代码 ``` cpp #include<cstdio> #include<cstring> #include<queue> const int maxn=6e5+5; inline int read(){ int x=0,fh=1; char ch=getchar(); while(ch<'0' || ch>'9'){ if(ch=='-') fh=-1; ch=getchar(); } while(ch>='0' && ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*fh; } int head[maxn],tot=1; struct asd{ int to,next; }b[maxn]; void ad(int aa,int bb){ b[tot].to=bb; b[tot].next=head[aa]; head[aa]=tot++; } struct jie{ int num; double jl; jie(){} jie(int aa,double bb){ num=aa,jl=bb; } bool operator < (const jie &A) const{ return jl>A.jl; } }; int n,m,du[maxn],cnt[maxn]; double sum[maxn],f[maxn]; bool vis[maxn]; std::priority_queue<jie> q; void dij(){ q.push(jie(n,0)); while(!q.empty()){ int now=q.top().num; q.pop(); if(vis[now]) continue; vis[now]=1; for(int i=head[now];i!=-1;i=b[i].next){ int u=b[i].to; if(vis[u]) continue; cnt[u]++; sum[u]+=f[now]; f[u]=(du[u]+sum[u])/cnt[u]; q.push(jie(u,f[u])); } } } int main(){ memset(head,-1,sizeof(head)); n=read(),m=read(); for(int i=1;i<=m;i++){ int aa,bb; aa=read(),bb=read(); ad(aa,bb); ad(bb,aa); du[aa]++,du[bb]++; } dij(); printf("%.10f\n",f[1]); return 0; } ```