【题解】Luogu P2081 [NOI2012]迷失游乐园

题解】Luogu P2081 [NOI2012]迷失游乐园"/>

【题解】Luogu P2081 [NOI2012]迷失游乐园

原题传送门

这是当时冬令营课上讲的题，咕咕咕到了现在

如果这题没有环套树的话，就很套路了

需要两个数组up[i]和down[i]，down[i]表示从i点第一步向下走的期望距离，up[i]表示从i点第一步向上走的期望距离，先求down，然后求up

\(down[i]=\frac{\sum_{j|son[i]}(down[j]+len(i,j))}{son[i]}\)

\(up[i]=\frac{up[fa[i]]+down[fa[i]]*son[fa[i]]-down[i]-len(fa[i],i)}{son[fa[i]]}+len(fa[i],i)\)

环套数就比较麻烦了qwqwq，但题目上告诉了我们一个环的特性：环长不超过20

那么方法也就很明了了，先将环上每个节点的子树的down处理出来，再枚举每个点，计算从这个点开始顺着环走的期望（因为不能回头，所以就是正反各搜一遍）

最后再更新每颗子树的up

最终答案就是每个节点up与down的和除以度数之和除以点数

程序中珂以再加上滚动数组，否则up和down很容易整错qwqwq

#include <bits/stdc++.h>
#define N 100005
#define db double
#define getchar nc
using namespace std;
inline char nc(){static char buf[100000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{register int x=0,f=1;register char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;
}
inline db Max(register db a,register db b)
{return a>b?a:b;
}
struct edge{int to,next,w;
}e[N<<1];
int head[N],cnt=0;
inline void add(register int u,register int v,register int w)
{e[++cnt]=(edge){v,head[u],w};head[u]=cnt;
}
int n,m,rt,tim;
int vis[N],cir[N],du[N],fa[N];
db d[N],f[N],g[N],tp[N];
db ans;
inline void dfs1(register int x)
{vis[x]=1;for(register int i=head[x];i;i=e[i].next)if(!vis[e[i].to]&&!cir[e[i].to]){dfs1(e[i].to);++du[x];d[x]+=f[e[i].to]+e[i].w;}if(du[x])f[x]=d[x]/(db)du[x];if(x!=rt)++du[x];
}
inline void dfs2(register int x)
{vis[x]=1;for(register int i=head[x];i;i=e[i].next)if(!vis[e[i].to]&&!cir[e[i].to]){d[e[i].to]+=(d[x]-f[e[i].to]-e[i].w)/Max(1,du[x]-1)+e[i].w;dfs2(e[i].to);}
}
inline void dfs3(register int x)
{vis[x]=++tim;for(register int i=head[x],j;i;i=e[i].next)if(e[i].to!=fa[x]){if(!vis[e[i].to]){fa[e[i].to]=x;dfs3(e[i].to);}else if(vis[e[i].to]<vis[x])for(cir[e[i].to]=1,j=x;j!=e[i].to;j=fa[j])cir[j]=1;   }
}
inline void dfs4(register int x,register int fa)
{bool flag=0;g[x]=0;for(register int i=head[x];i;i=e[i].next)if(e[i].to!=rt&&e[i].to!=fa&&cir[e[i].to]){flag=1;dfs4(e[i].to,x);g[x]+=g[e[i].to]+e[i].w;}if(x==rt)return;int k=du[x];k?k:++k;if(!flag)g[x]=d[x]/(db)k;elsek=du[x]+1,g[x]=(g[x]+d[x])/(db)k;
}
int main()
{n=read(),m=read();for(register int i=1;i<=m;++i){int u=read(),v=read(),w=read();add(u,v,w),add(v,u,w);}if(m==n-1){rt=1;dfs1(1);memset(vis,0,sizeof(vis));dfs2(1);}else{dfs3(1);memset(vis,0,sizeof(vis));for(register int i=1;i<=n;++i)if(cir[i])rt=i,dfs1(i);for(register int i=1;i<=n;++i)if(cir[i]){rt=i;dfs4(i,0);tp[i]=g[i];}memset(vis,0,sizeof(vis));for(register int i=1;i<=n;++i)if(cir[i])du[i]+=2,d[i]+=tp[i];for(register int i=1;i<=n;++i)if(cir[i])rt=i,dfs2(i);}for(register int i=1;i<=n;++i)ans+=d[i]/(db)du[i];printf("%.5lf",ans/(db)n);return 0;
}

转载于:.html