NOI2012 迷失游乐园

题目:

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

思路:

   也就是基环树,先考虑树的情况。
  对于每个点,先做一次dfs处理出每个点向子树中走的期望距离。再做一次dfs,再做一次dfs加上向子树外走的贡献,只加入用父亲为起点的期望距离消除走入当前这棵子树的期望距离的贡献即可。
  再考虑基环树,按照基环树的套路,先把环拎出来。观察发现,除了环上的点以外,计算其他的点还是一样的做法。所以只要考虑如何算出环上的每个点为起点时的期望距离,对于环上的每一个点,它在环上走的情况就是:有 的概率走向下一个点,有 的概率走入子树中( 的度, 不能是当前点,当前点不能走入子树中)。分别计算出两个方向沿着环走期望距离,再加上往子树内走的期望距离就能求出环上的每个点为起点时的期望距离了。
  ps:感觉自己写的复杂了,貌似网上的题解都没有这么长。

代码:

#include <bits/stdc++.h>
#define _(...) (void)(__VA_ARGS__)
#define rep(i,a,b) for(int i(a),i##_END_(b);i<=i##_END_;i++)
#define drep(i,a,b) for(int i(a),i##_END_(b);i>=i##_END_;i--)
template<class T> inline bool tomax(T &a,T b){return a<b?a=b,1:0;}
template<class T> inline bool tomin(T &a,T b){return b<a?a=b,1:0;}
typedef long long ll;

const int N=1e5+5;

#define erep(k,G,o) for(int k=G.HEAD[o];k;k=G.NXT[k])
template<int N,int M,class T> struct Link{
    int HEAD[N],NXT[M],tot;T W[M];
    void add(int x,T w){NXT[++tot]=HEAD[x];W[HEAD[x]=tot]=w;}
    T& operator [] (int x){return W[x];}
};
struct Edge{
    int to,w;
};
Link<N,N<<1,Edge> G;

double dp[N];
int cnt[N],n;
bool mark[N];
void dfs(int o,int f){
    erep(k,G,o)
        cnt[o]+=(G[k].to!=f&&!mark[G[k].to]);
    erep(k,G,o){
        Edge e=G[k];
        if(e.to==f||mark[e.to])continue;
        dfs(e.to,o);
        dp[o]+=(dp[e.to]+e.w)/cnt[o];
    }
}
void redfs(int o,int f){
    int w;
    erep(k,G,o)
        if(G[k].to==f)
            w=G[k].w;
    if(f!=0){
        double fa=dp[f];
        fa-=(dp[o]+w)/cnt[f];
        if(cnt[f]>1)fa=fa*cnt[f]/(cnt[f]-1);
        dp[o]=dp[o]*cnt[o]/(cnt[o]+1);
        dp[o]+=(fa+w)/(cnt[o]+1);
        cnt[o]++;
    }
    erep(k,G,o)
        if(G[k].to!=f&&!mark[G[k].to])
            redfs(G[k].to,o);
}

namespace Subtask1{
    void solve(){
        dfs(1,0);redfs(1,0);
        double ans=0;
        rep(i,1,n)
            ans+=dp[i]/n;
        printf("%.6lf\n",ans);
    }
}
namespace Subtask2{
    int stk[N],top,vec[30],tot;
    bool vis[N];
    bool dfs_circle(int o,int f){
        if(vis[o]){
            do {
                mark[stk[top]]=true;
                vec[++tot]=stk[top];
            }while(stk[top--]!=o);
            return true;
        }
        stk[++top]=o;vis[o]=true;
        erep(k,G,o){
            int v=G[k].to;
            if(v==f)continue;
            if(dfs_circle(v,o))return true;
        }
        top--;
        return false;
    }
    int nxt[N][2],ton[N][2];
    double dp_c[N][2];
    double calc(int x,int t,int d){
        if(nxt[x][d]==t)return dp[x];
        return (calc(nxt[x][d],t,d)+ton[x][d]+dp[x]*cnt[x])/(cnt[x]+1);
    }
    void solve(){
        dfs_circle(1,0);
        rep(i,1,tot){
            int o=vec[i];
            nxt[o][0]=vec[(i-1-1+tot)%tot+1];
            nxt[o][1]=vec[(i-1+1+tot)%tot+1];
            erep(k,G,o){
                int v=G[k].to;
                if(v==nxt[o][0])
                    ton[o][0]=G[k].w;
                else if(v==nxt[o][1])
                    ton[o][1]=G[k].w;
            }
            dfs(o,0);
        }
        rep(i,1,tot){
            int o=vec[i];
            dp_c[o][0]=calc(o,nxt[o][1],0);
            dp_c[o][1]=calc(o,nxt[o][0],1);
        }
        rep(i,1,tot){
            int o=vec[i];
            dp[o]=dp[o]*cnt[o]/(cnt[o]+2);
            dp[o]+=(dp_c[nxt[o][0]][0]+ton[o][0])/(cnt[o]+2);
            dp[o]+=(dp_c[nxt[o][1]][1]+ton[o][1])/(cnt[o]+2);
            cnt[o]+=2;
            redfs(o,0);
        }
        double ans=0;
        rep(i,1,n)
            ans+=dp[i];
        printf("%.6lf\n",ans/n);
    }
}

int main(){
    int m;
    scanf("%d%d",&n,&m);
    rep(i,1,m){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        G.add(a,(Edge){b,c});
        G.add(b,(Edge){a,c});
    }
    if(m==n-1)Subtask1::solve();
    else Subtask2::solve();
    return 0;
}