[NOI2012]迷失游乐园

游乐园"/>

[NOI2012]迷失游乐园

传送门

Description

基环树上随机选择一个点做起点，等概率向其相邻的节点移动，保证每个点只经过不超过\(1\)次

求期望的最大游走距离

Solution

假设环处在最上面的位置

设\(down_x\)表示向下走的期望距离，\(up_x\)表示向上走的期望距离

那么如果是树的话
\[ down_x=\sum \frac{w(E<x,son_i>)+down_{son_i}}{degree_x-1} \]

\[ up_x=\frac{up_{fa}+down_{fa}*(degree_{fa}-1-w(E<x,fa>)-down[x])}{degree_{fa}-1} \]

对于环，其实求\(down_x\)的部分是不会变得

考虑如果求得了环上每个点的\(up\)，那么外向树上的点\(up\)值可以类似树的方式求得

对于环上一个点：

首先它有可能往逆时针或顺时针走，概率相等

对于一个方向，它有可能顺着环走到一个点后开始向下走，进入该点的子树

求出到这个点的概率，再乘上它的\(down\)值

Code 

#include<bits/stdc++.h>
#define reg register
#define db double
inline int read()
{reg int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}
const int MN=1e5+5;
int N,M,d[MN],son[MN];
struct edge{int to,w,nex;}e[MN<<1];
int hr[MN],en;
void ins(int x,int y,int w)
{e[++en]=(edge){y,w,hr[x]};hr[x]=en;e[++en]=(edge){x,w,hr[y]};hr[y]=en;
}
db down[MN],up[MN],ans;
bool vis[MN],inr[MN],flag;
int st[MN],last[MN],tp,cir[MN],num;
void tj(int x,int f)
{if(flag) return;vis[x]=true;st[tp++]=x;reg int i;for(i=hr[x];i;i=e[i].nex) if(f^e[i].to&&!flag)if(!vis[e[i].to]) last[e[i].to]=e[i].w,tj(e[i].to,x);else{last[e[i].to]=e[i].w;for(;st[tp]!=e[i].to;--tp)inr[cir[num++]=st[tp-1]]=true;flag=true;return;}if(st[tp-1]==x) --tp;
}
void dfs1(int x,int f)
{//downreg int i;for(i=hr[x];i;i=e[i].nex)if((f^e[i].to)&&!inr[e[i].to])++son[x],dfs1(e[i].to,x),down[x]+=e[i].w+down[e[i].to];if(son[x])down[x]/=(db)son[x];
}
int Rt;
void dfs2(int x,int f,int len=0)
{//upreg int i;if(x!=Rt) up[x]=len+(db)(up[f]*(d[f]-son[f])+down[f]*son[f]-len-down[x])/(db)(d[f]>1?d[f]-1:1);for(i=hr[x];i;i=e[i].nex)if((f^e[i].to)&&!inr[e[i].to]) dfs2(e[i].to,x,e[i].w);
}
int main()
{N=read();M=read();reg int i,j,x,y;for(i=1;i<=M;++i) x=read(),y=read(),ins(x,y,read()),++d[x],++d[y];if(M==N-1) dfs1(1,0),dfs2(Rt=1,0);else{tj(1,0);for(i=0;i<num;++i) dfs1(cir[i],0);for(i=0;i<num;++i){db p1=.5,p2=.5,s1=(db)last[cir[i]],s2=0.;for(j=1;j<num;++j){x=(i+j)%num;y=(i-j+num)%num;s2+=(db)last[cir[y]];if(j==num-1){up[cir[i]]+=p1*(s1+down[cir[x]]);up[cir[i]]+=p2*(s2+down[cir[y]]);break;}up[cir[i]]+=p1*((db)son[cir[x]]/(db)(d[cir[x]]-1))*(s1+down[cir[x]]);p1*=1./(d[cir[x]]-1);up[cir[i]]+=p2*((db)son[cir[y]]/(db)(d[cir[y]]-1))*(s2+down[cir[y]]);p2*=1./(d[cir[y]]-1);s1+=(db)last[cir[x]];}}for(i=0;i<num;++i) dfs2(Rt=cir[i],0);}for(i=1;i<=N;++i)ans+=(up[i]*(db)(d[i]-son[i])+down[i]*(db)son[i])/(db)d[i];ans/=(db)N;printf("%.5lf\n",ans);return 0;
}

Blog来自PaperCloud，未经允许，请勿转载，TKS！

转载于:.html