Qiuly

「NOI2012」迷失游乐园 基环树+DP luoguP2081
先考虑树的情况。对于一个点 $i$ ,设 $ans_i$ 表示以 $i$ 为起点的路径的期望长度,$f_i$ 表示...
扫描右侧二维码阅读全文
21
2019/10

「NOI2012」迷失游乐园 基环树+DP luoguP2081

先考虑树的情况。

对于一个点 $i$ ,设 $ans_i$ 表示以 $i$ 为起点的路径的期望长度,$f_i$ 表示 $i$ 往子树走的路径的期望长度,$g_i$ 表示 $i$ 往父亲及上面节点走的路径的期望长度,$du_{i}$ 表示 $i$ 的儿子个数,那么有转移:

$$ \begin{cases} f_{u}=\frac{1}{du_u}\sum\limits_{v\in son_{u}}\left(w(u,v)+f_{v}\right)\\ g_{u}=w(fa_u,u)+\frac{g_{fa_u}+du_{fa_u}f_{fa_u}-w(fa_{u},u)-f_{u}}{du_{fa_{u}}-[fa_{u}=root]}\\ ans_{u}=\frac{1}{du_u+[u\not=root]}(du_uf_{u}+g_{u}) \end{cases} $$

这样子随便搞搞就好了。


然后考虑基环树的情况。基环树长下面那样:

基环树

显然,对于环上的节点(即红色点),每一次"往上走"会有两个选项,转移方式将会改变。对于蓝色节点,可以将环上节点看作一个小树的根,那么这样蓝色节点的 $\rm{DP}$ 就可以按照原来的方式计算。

将每一个红色点的相邻的两个红色点看作这个红色点"上面的节点",这样所有节点的 $f$ 都可以直接算,对于 $g$ 的话,因为转移需要用到父节点的 $g$ ,所以现在需要先处理红色点的 $g$ 。

发现红色点的个数不超过 $20$ ,暴力走即可。就是说对于一个红色点,暴力走环。如果走到当前点后,进入当前红点的子树和接着走向下一个红点的贡献都很好算,然后走了一圈后回到了原来的节点,贡献就算完了,这里复杂度因该是 $O(m^2)$ ,其中 $m$ 是红色点的个数。

显然这是可以很轻松水过的。

#if By_Qiuly
We're here to put a dent in the universe. Otherwise why else even be here?
(FAKE)solution(baoli) : 
algorithm : 
#endif

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=1e5+5;

double f[N],g[N];
int n,m,cnt,head[N];
int tim,dfn[N],siz[N],cir[N],pre[N];
struct Edge{int nxt,to,val;} G[N<<1];
inline void addedge(int u,int v,int w) {G[++cnt]=(Edge){head[u],v,w},head[u]=cnt;}

template <typename T> inline void IN(T&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

namespace Circle {
    void find(int u) {
        dfn[u]=++tim;
        for(int i=head[u],v;i;i=G[i].nxt) if((v=G[i].to)^pre[u]) {
            if(!dfn[v]) pre[v]=u,find(v);
            else if(dfn[v]<dfn[u]) {
                for(int j=u;j!=v;j=pre[j]) cir[j]=true;
                cir[v]=true;goto end;
            }
        }end:;
    }
    void dfs1(int u,int fa) {
        for(int i=head[u],v;i;i=G[i].nxt) 
            if((v=G[i].to)^fa&&!cir[v]) ++siz[u],dfs1(v,u),f[u]+=G[i].val+f[v];
        if(siz[u]) f[u]/=siz[u];
    }
    double calc(int u,int fa,int sta) {
        for(int i=head[u],v;i;i=G[i].nxt)
            if((v=G[i].to)^fa&&cir[v]) {
                if(v==sta) return f[u];
                else return (calc(v,u,sta)+G[i].val+f[u]*siz[u])/(siz[u]+1);
            }
        return 0.0;
    }
    inline void solve(int u) {
        for(int i=head[u],v;i;i=G[i].nxt) 
            if(cir[v=G[i].to]) g[u]+=calc(v,u,u)+G[i].val;
        g[u]/=2;
    }
    void dfs2(int u,int fa) {
        for(int i=head[u],v;i;i=G[i].nxt) 
            if((v=G[i].to)^fa&&!cir[v]) {
                if(cir[u]) g[v]=G[i].val+(g[u]*2+f[u]*siz[u]-f[v]-G[i].val)/(siz[u]+1);
                else g[v]=G[i].val+(g[u]+f[u]*siz[u]-f[v]-G[i].val)/siz[u];
                dfs2(v,u);
            }
    }
    inline void Main() {
        find(1);
        for(int i=1;i<=n;++i) if(cir[i]) dfs1(i,0);
        for(int i=1;i<=n;++i) if(cir[i]) solve(i);
        for(int i=1;i<=n;++i) if(cir[i]) dfs2(i,0);
        double ans=0;
        for(int i=1;i<=n;++i) {
            if(cir[i]) ans+=(g[i]*2+f[i]*siz[i])/(siz[i]+2);
            else ans+=(g[i]+f[i]*siz[i])/(siz[i]+1);
        }
        ans/=n,printf("%.6lf\n",ans);
    }
}

namespace Tree {
    void dfs1(int u,int fa) {
        for(int i=head[u],v;i;i=G[i].nxt) if((v=G[i].to)^fa)
            ++siz[u],dfs1(v,u),f[u]+=G[i].val+f[v];
        if(siz[u]) f[u]/=siz[u];
    }
    void dfs2(int u,int fa) {
        double tmp=g[u]+f[u]*siz[u];
        for(int i=head[u],v;i;i=G[i].nxt) if((v=G[i].to)^fa) {
            if(u==1) {
                if(siz[u]==1) g[v]=G[i].val;
                else g[v]=G[i].val+(tmp-f[v]-G[i].val)/(siz[u]-1);
            } else g[v]=G[i].val+(tmp-f[v]-G[i].val)/siz[u];
            dfs2(v,u);
        }
    }
    inline void Main() {
        dfs1(1,0),dfs2(1,0);
        double ans=f[1];
        for(int i=2;i<=n;++i) ans+=(g[i]+f[i]*siz[i])/(siz[i]+1);
        ans/=n,printf("%.6lf\n",ans);
    }
}

int main() {
    IN(n),IN(m);
    for(int i=1,u,v,w;i<=m;++i)
        IN(u),IN(v),IN(w),addedge(u,v,w),addedge(v,u,w);
    if(m==n-1) Tree::Main();
    else Circle::Main();
    return 0;
}
最后修改:2019 年 10 月 22 日 08 : 51 PM

发表评论