Noi2012|Noi2012 迷失游乐园 Noi2012迷失游乐园

题目描述：
bz
luogu
题解：
树形$dp$+基环树上树形$dp$。
考虑$n-1=m$即形成一棵树时怎么做。
【Noi2012|Noi2012 迷失游乐园】设$d[x]$表示$x$的度数，$ch[x]$表示$x$的儿子数。
$dn[x]$表示$x$向下走的期望长度（在环上指向树的方向走），$up[x]$表示$x$向上走的期望长度（在环上指向环上的相邻点走）。
$f$表示$x$在树上的父亲。
在树上有这几个递推式：
$$dn[x]=\frac{\sum_{(x,v)}dn[v]+w(x,v)}{ch[i]}$$
$$up[x]=w(f,x)+\frac{dn[f]*ch[f]-w(f,x)-dn[x]+up[f]*(f!=rt)}{d[f]-1}$$
$$ans=\frac{\sum_{i=1}^{n}{\frac{dn[i]*ch[i]+up[i]*(i!=rt)}{d[f]-1}}}{n}$$
注意分母等于$0$的情况。
树形$dp$即可。
考虑把这个东西搬到基环树上。
我们可以把环拎起来，这个东西就变成几棵树的根用环上的几条边连起来。
先用上面那个式子把$dn$求出来，
然后考虑如何把$up$搞出来。
显然一个环上的点在环上走只能有两个方向，那么就可以分方向讨论一下。
由于环上最多$20$个点，我们可以枚举。
把环上的点的$up$搞出来就可以树形$dp$了。
注意要把上面的式子$(f!=rt)$去掉。
最后统计一下就行了。
代码：

文章图片

文章图片

#include #include #include using namespace std; const int N = 100050; const double eps = 1e-7; template inline void read(T&x) { T f = 1,c = 0; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){c=c*10+ch-'0'; ch=getchar(); } x = f*c; } int n,m,hed[N],cnt=1; struct EG { int to,nxt,w; }e[2*N]; void ae(int f,int t,int w) { e[++cnt].to = t; e[cnt].nxt = hed[f]; e[cnt].w = w; hed[f] = cnt; } double up[N],dn[N],d[N],ch[N]; int sta[N],ste[N],rt,tl; bool vis[N],cir[N]; double dfs1(int u,int f) { for(int j=hed[u]; j; j=e[j].nxt) { int to = e[j].to; if(to==f||cir[to])continue; dn[u]+=dfs1(to,u)+e[j].w; } if(ch[u]>eps)dn[u]/=ch[u]; return dn[u]; } void dfs2(int u,int f) { for(int j=hed[u]; j; j=e[j].nxt) { int to = e[j].to; if(to==f||cir[to])continue; up[to] = e[j].w; if(d[u]-1.0>eps)up[to] += (dn[u]*ch[u]-e[j].w-dn[to]+up[u]*(d[u]-ch[u]))/(d[u]-1.0); dfs2(to,u); } } int dfss(int u,int pre) { if(vis[u]) { rt = u; return 1; } vis[u] = 1; for(int now,j=hed[u]; j; j=e[j].nxt) { int to = e[j].to; if(j==pre)continue; if((now=dfss(to,j^1))) { if(now==1) { sta[++tl] = u; ste[tl] = e[j].w; cir[u] = 1; if(u!=rt)return 1; } return 2; } } return 0; } int lf(int i) { if(i!=1)return i-1; return tl; } int rg(int i) { if(i!=tl)return i+1; return 1; } int main() { //freopen("tt.in","r",stdin); read(n),read(m); for(int f,t,w,i=1; i<=m; i++) { read(f),read(t),read(w); ae(f,t,w),ae(t,f,w); d[f]+=1,d[t]+=1; } if(n>m) { ch[1]=d[1]; for(int i=2; i<=n; i++)ch[i]=d[i]-1; dfs1(1,0); dfs2(1,0); double ans = 0.0; for(int i=1; i<=n; i++) ans += (dn[i]*ch[i]+up[i]*(i!=1))/d[i]; ans/=n; printf("%.5lf\n",ans); return 0; } dfss(1,0); for(int i=1; i<=n; i++)ch[i]=d[i]-(cir[i]?2:1); for(int i=1; i<=tl; i++) dfs1(sta[i],0); for(int i=1; i<=tl; i++) { double u0 = 0.0,now = 1.0/2; for(int j=lf(i); j!=i; j=lf(j)) { if(j!=rg(i))u0 += now*(ste[rg(j)]+dn[sta[j]]*ch[sta[j]]/(ch[sta[j]]+1.0)); else u0 += now*(ste[rg(j)]+dn[sta[j]]); now *= 1.0/(ch[sta[j]]+1.0); } up[sta[i]] += u0; u0 = 0.0,now = 1.0/2; for(int j=rg(i); j!=i; j=rg(j)) { if(j!=lf(i))u0 += now*(ste[j]+dn[sta[j]]*ch[sta[j]]/(ch[sta[j]]+1.0)); else u0 += now*(ste[j]+dn[sta[j]]); now *= 1.0/(ch[sta[j]]+1.0); } up[sta[i]] += u0; dfs2(sta[i],0); } double ans = 0.0; for(int i=1; i<=n; i++) ans += (dn[i]*ch[i]+up[i]*(d[i]-ch[i]))/d[i]; printf("%.5lf\n",ans/n); return 0; }

View Code
转载于:https://www.cnblogs.com/LiGuanlin1124/p/10801562.html