呀～期望真的是很难呢～～

Problem

放假了，小 Z 觉得呆在家里特别无聊，于是决定一个人去游乐园玩。

进入游乐园后，小 Z 看了看游乐园的地图，发现可以将游乐园抽象成有 n 个景点、m 条道路的无向连通图，且该图中至多有一个环（即 m 只可能等于 n 或者 n -1）。小 Z 现在所在的大门也正好是一个景点。小 Z 不知道什么好玩，于是他决定，从当前位置出发，每次随机去一个和当前景点有道路相连的景点，并且同一个景点不去两次（包括起始景点）。贪玩的小 Z 会一直游玩，直到当前景点的相邻景点都已经访问过为止。

小 Z 所有经过的景点按顺序构成一条非重复路径，他想知道这条路径的期望长度是多少？

小 Z 把游乐园的抽象地图画下来带回了家，可是忘了标哪个点是大门，他只好假设每个景点都可能是大门（即每个景点作为起始点的概率是一样的）。同时，他每次在选择下一个景点时会等概率地随机选择一个还没去过的相邻景点。

Solution

考虑树，可以得到一个简单的树型 dp：$f_i=(\sum_{son} f_{son}+W_{(i,son)})/siz$，$siz$ 是儿子个数。对于叶子节点应当特别的计算一下。

考虑基环树。对于环上的某个点，如果点顺时针走，则逆时针方向的第一条边不会被遍历，否则顺时针方向的第一条边不会被遍历。显然对于点连接的子树也是同样的道理。这给了我们一个断边跑 dp 的思路（因为环上点的个数较少）。

对于环上的每个点和子树，它们应当总共只会被统计两次（断相邻的两条边），同时应注意即使断开了边，初始选择方向的概率仍不应该忽略，而再一次到达删去边的旁边这个概率应当忽略。

所以我们每次选择断环上一条边，统计边上两个点和其子树的概率，然后再将环上的边全部断开，删去两条边都不经过的被重复统计的情况。

细节较多，因此代码也较丑。

Code

// Code by ajcxsu
// Problem: lost in amusement park

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10, M=2e5+10;
int h[N], to[M], nexp[M], W[M], p=2;
char del[M];
inline void ins(int a, int b, int w) { nexp[p]=h[a], h[a]=p, to[p]=b, W[p]=w, p++; }

long double f[N], ans;
int son[N];

int very(int x) { return x==0?1:x; }
void dfs1(int x, int fr, int con=0) {
    int siz=con;
    f[x]=0;
    for(int u=h[x];u;u=nexp[u])
        if(to[u]!=fr && !del[u]) dfs1(to[u], x), f[x]+=f[to[u]]/very(son[to[u]])+W[u], ++siz;
    if(siz) son[x]=siz;
}

int nd[N], cir[N], fa[N], e[N], idx;
char vis[N], flag;
double de[N]; // debug
void dfs2(int x, int fr, int d=1) {
    ans+=f[x]/very(son[x])*d;
    de[x]+=f[x]/very(son[x])*d;
    long double b1=f[x], b2;
    for(int u=h[x];u;u=nexp[u])
        if(to[u]!=fr && !cir[to[u]]) {
            b2=f[to[u]];
            f[x]-=f[to[u]]/very(son[to[u]])+W[u], son[x]--;
            f[to[u]]+=f[x]/very(son[x])+W[u], son[to[u]]++;
            dfs2(to[u], x, d);
            f[to[u]]=b2, f[x]=b1, son[x]++, son[to[u]]--;
        }
}
void dfs3(int x, int fr) {
    vis[x]=1;
    for(int u=h[x];u && !flag;u=nexp[u])
        if(to[u]!=fr) {
            fa[to[u]]=x, e[to[u]]=u;
            if(!vis[to[u]]) dfs3(to[u], x);
            else {
                int na=x;
                do { cir[na]=++idx, nd[idx]=na, na=fa[na]; } while(na!=x);
                flag=1;
            }
        }
    vis[x]=0;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cout.setf(ios::fixed), cout<<setprecision(5);
    int n, m;
    cin>>n>>m;
    int u, v, w;
    for(int i=0;i<m;i++) cin>>u>>v>>w, ins(u, v, w), ins(v, u, w);
    if(m==n-1) {
        dfs1(1, 0), dfs2(1, 0), cout<<ans/n<<endl;
        exit(0);
    }
    dfs3(1, 0);
    for(int i=1;i<=idx;i++) {
        del[e[nd[i]]]=del[e[nd[i]]^1]=1,
        dfs1(nd[i], 0, 1), dfs2(nd[i], 0), dfs1(fa[nd[i]], 0, 1), dfs2(fa[nd[i]], 0);
        del[e[nd[i]]]=del[e[nd[i]]^1]=0;
    }
    for(int i=1;i<=idx;i++) del[e[nd[i]]]=del[e[nd[i]]^1]=1;
    for(int i=1;i<=idx;i++) dfs1(nd[i], 0, 2), dfs2(nd[i], 0, -1);
    ans/=n;
    cout<<ans<<endl;
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-2081.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆