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

博客迁移计划2

$\rightarrow $ 戳我进洛谷原题

[Noi2012]迷失游乐园

Time Limit: 10 Sec Memory Limit: 512 MB

Description

放假了，小Z觉得呆在家里特别无聊，于是决定一个人去游乐园玩。
进入游乐园后，小Z看了看游乐园的地图，发现可以将游乐园抽象成有 $ n $ 个景点、$ m $条道路的无向连通图，
且该图中至多有一个环（即 \(m\) 只可能等于 \(n\) 或者 \(n-1\) ）。
小Z现在所在的大门也正好是一个景点。
小Z不知道什么好玩，于是他决定，从当前位置出发，每次随机去一个和当前景点有道路相连的景点，
并且同一个景点不去两次（包括起始景点）。
贪玩的小Z会一直游玩，直到当前景点的相邻景点都已经访问过为止。
小Z所有经过的景点按顺序构成一条非重复路径，他想知道这条路径的期望长度是多少？
小Z把游乐园的抽象地图画下来带回了家，可是忘了标哪个点是大门，
他只好假设每个景点都可能是大门（即每个景点作为起始点的概率是一样的）。
同时，他每次在选择下一个景点时会等概率地随机选择一个还没去过的相邻景点。
　

Input

第一行是两个整数 \(n\) 和 \(m\) ，分别表示景点数和道路数。
接下来行，每行三个整数\(X_i,Y_i,W_i\) ，分别表示第 \(i\) 条路径的两个景点为 \(X_i,Y_i\) ，路径长 \(W_i\) 。
所有景点的编号从 \(1\) 至 \(n\) ，两个景点之间至多只有一条道路。

Output

共一行，包含一个实数，即路径的期望长度，保留五位小数

　

Sample Input

 4 3 
 1 2 3 
 2 3 1 
 3 4 4

Sample Output

6.00000

HINT

【样例解释】样例数据中共有\(6\)条不同的路径:

路径	长度	概率
\(1\rightarrow 4\)	\(8\)	\(\frac{1}{4}\)
\(2\rightarrow 1\)	\(3\)	\(\frac{1}{8}\)
\(2\rightarrow 4\)	\(5\)	\(\frac{1}{8}\)
\(3\rightarrow 1\)	\(4\)	\(\frac{1}{8}\)
\(3\rightarrow 4\)	\(4\)	\(\frac{1}{8}\)
\(4\rightarrow 1\)	\(8\)	\(\frac{1}{4}\)

因此期望长度\(= \frac{8}{4} + \frac{3}{8} + \frac{5}{8} + \frac{4}{8} + \frac{4}{8} + \frac{8}{4} = 6.00\)
　
【评分方法】

本题没有部分分，你程序的输出只有和标准答案的差距不超过\(0.01\)时，才能获得该测试点的满分，否则不得分。

【数据规模和约定】

对于\(100\%\)的数据，\(1 \le W_i \le 100\)。

测试点编号	nnn	mmm	备注
\(1\)	\(n=10\)	\(m = n-1\)	保证图是链状
\(2\)	\(n=100\)	\(m=n−1\)	只有节点\(1\)的度数大于\(2\)
\(3\)	\(n=1000\)	\(m=n−1\)	/
\(4\)	\(n=10^5\)	\(m=n−1\)	/
\(5\)	\(n=10^5\)	\(m=n−1\)	/
\(6\)	\(n=10\)	\(m=n\)	/
\(7\)	\(n=100\)	\(m=n\)	环中节点个数\(\leq 5\)
\(8\)	\(n=1000\)	\(m=n\)	环中节点个数\(\leq 10\)
\(9\)	\(n=10^5\)	\(m=n\)	环中节点个数\(\leq 15\)
\(10\)	\(n=10^5\)	\(m=n\)	环中节点个数\(\leq 20\)

---

题解

• $ 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]+=\frac{D[x]-F[y]-w(x,y)}{deg[x]-1}+w(x,y) , \quad G[y]=\frac{D[y]}{deg[y]}$

　

• $ 100 $ % 的基环树数据

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

　

• 分别以环以外的每个点 \(p\) 作为起点

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

• $ G[p]=\frac{D[p]+calcL(l_p)+w(p,l_p)+calcR(r_p)+w(p,r_p)}{deg[p]}$

• $ calcL(x)=\frac{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;
}