[NOI2012] 迷失游乐园 概率 期望 基环树DP

$ \rightarrow $ 戳我进洛谷原题 $ \rightarrow $ 戳我进bzoj原题

• $ N $ 个点，不超过 $ N $ 条边的连通图。

• 从每个点出发一直走下去，不能重复经过某个点，其他点等概率随机选择。

• 问走过的路径长度的数学期望是多少？

• $ N \le 100000 $ 。图中至多只有一个环，并且环长不超过20.

• 有 $ 50 $ % 的数据，$ N-1 $ 条边。

• 有 $ 50 $ % 的数据，$ N $ 条边。

• $ 50% $的树形数据

• 任选 $ 1 $ 号点为根，做树形 $ DP $

• 设点 $ x $ 作为起点，期望长度 $ G[x] $ ，只走向子树，期望长度 $ F[x] $

• 第一次树形 $ DP $，通过子节点 $ s_i $ 计算 $ x $

• 设 $ D[x]=\Sigma (F[s_i]+w(x,s_i)) $.则 $ F[x]=D[x]/deg[x] $

• 第二次树形$ DP $，通过父节点 $ x $ 计算 $ y $

• $ D[y]+=(D[x]-F[y]-w(x,y))/(deg[x]-1)+w(x,y) , G[y]=D[y]/deg[y] $

• $ 100 $ % 的基环树数据

• 除了环以外的子树，第一次树形 $ DP $ 求出 $ F[x],D[x] $

• 分别以环以外的每个点 $ p $ 作为起点

• 分别以逆时针、顺时针两个方向递归遍历整个环

• $ G[p]=(D[p]+calcL(l_p)+w(p,l_p)+calcR(r_p)+w(p,r_p))/deg[p]

• calcL(x)=(D[x]+calcL(l_x)+w(x,l_x))/(deg[x]-1)

• 得到环上每个点的 $ G $ 后，再做第二次树形 $ DP $ 更新子树中的 $ G $

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
#define maxn 100005
#define PP pair<int,int>
#define mp(a,b) make_pair(a,b)
#define fi first
#define se second
#define pb(x) push_back(x)
inline int read() {
    register char ch;
    while(!isdigit(ch=getchar()));
    register int x=ch^'0';
    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
    return x;
}
vector<PP>E[maxn];
int n,m,vis[maxn],tim,fa[maxn],deg[maxn],root;
double ans,D[maxn],F[maxn],G[maxn],tmp[maxn];
bool cir[maxn];
void dfs1(int u,int pre){
    vis[u]=1;
    for(int i=0;i<E[u].size();++i){
        int v=E[u][i].fi,w=E[u][i].se;
        if(v!=pre&&!cir[v]){
            dfs1(v,u); 
            ++deg[u]; 
            D[u]+=F[v]+w;
        }
    }
    F[u]=D[u]/(double)max(1,deg[u]);
    if(u!=root) ++deg[u];
}
void dfs2(int u,int pre){
    vis[u]=1;
    for(int i=0;i<E[u].size();++i){
        int v=E[u][i].fi,w=E[u][i].se;
        if(v!=pre&&!cir[v]){
            D[v]+=(D[u]-F[v]-w)/(double)max(1,deg[u]-1)+w;
            dfs2(v,u);
        }
    }
}
void dfs3(int u){
    vis[u]=1;
    for(int i=0,j;i<E[u].size();++i){
        int v=E[u][i].fi;
        if(v!=fa[u]){
            if(!vis[v]){ fa[v]=u; dfs3(v); }
            else if(!cir[v])
                for(cir[v]=1,j=u;j!=v;j=fa[j])
                    cir[j]=1;
        }
    }
}
void dfs4(int u,int pre){
    bool flag=0; G[u]=0;
    for(int i=0;i<E[u].size();++i){
        int v=E[u][i].fi,w=E[u][i].se;
        if(v!=root&&v!=pre&&cir[v]){
            flag=1; dfs4(v,u);
            G[u]+=G[v]+w;
        }
    }
    if(u==root) return;
    int k=deg[u];
    if(!flag) G[u]=D[u]/(double)max(1,k);
    else{ k=deg[u]+1; G[u]=(G[u]+D[u])/(double)k; }
}
int main(){
    n=read(); m=read();
    for(int i=1;i<=m;++i){
        int x,y,w; x=read(); y=read(); w=read();
        E[x].pb(mp(y,w));
        E[y].pb(mp(x,w));
    }
    if(m==n-1){
        root=1;
        dfs1(1,0);
        dfs2(1,0);
    } else {
        dfs3(1); 
        for(int i=1;i<=n;++i) if(cir[i]){ root=i; dfs1(i,0); }
        for(int i=1;i<=n;++i) if(cir[i]){ root=i; dfs4(i,0); tmp[i]=G[i]; }
        for(int i=1;i<=n;++i) if(cir[i]){ deg[i]+=2; D[i]+=tmp[i]; }
        for(int i=1;i<=n;++i) if(cir[i]){ root=i; dfs2(i,0); } 
    }
    for(int i=1;i<=n;++i) ans+=D[i]/(double)deg[i]; 
    printf("%.5lf",ans/(double)n);
    return 0;
}

[NOI2012] 迷失游乐园 概率 期望 基环树DP

原文：https://www.cnblogs.com/PotremZ/p/9419035.html