Noi2012 迷失游乐园

游乐园"/>

Noi2012 迷失游乐园

题目描述：

bz

luogu

题解：

树形$dp$+基环树上树形$dp$。

考虑$n-1=m$即形成一棵树时怎么做。

设$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<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100050;
const double eps = 1e-7;
template<typename T>
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;
}

转载于:.html