枫林晚 的博客

枫林晚 的博客

[NOI2012]迷失游乐园

posted on 2018-09-05 15:20:19 | under 未分类 |

安利cnblog博客:[Noi2012]迷失游乐园

比较麻烦的图论期望题。

花费3hWA一次,然后AC了此题。

和网上的题解大致差不多。肯定也要分树形和基环树两种情况讨论。

首先考虑树的:

本人没有用什么up数组。只有一个E[x],P[x]

表示,从x往下走的期望长度。到点X的概率。 树

对于一棵树,直接dfs1,找到以1为根的信息。

然后换根即可。dfs2就是换根、。

ans[x]={ len[fa]+(ans[fa]-(E[x]/P[x]+len[fa])×1/d[fa])×d[fa]/(d[fa]-1) }×1/d[x] + E[x]/P[x] × (d[x]-1)/d[x]

len[fa]表示,x到fa的边的长度。ans[i]表示,从i出发的期望长度。

貌似非常复杂。因为少记一个up嘛。

就是,算了两个部分,x向上走到fa的贡献,和向下走到儿子的贡献

前半部分向上走的:

算ans[fa]抛去x的部分:E[x]/P[x],把x向下走的贡献变成P[x]=1的贡献,然后加上len[fa],再乘上fa到x的概率,就是1/d[fa]

减掉之后,由于其他部分,从ans[x]出发,每个点的概率是1/d[fa]的,但是,现在fa不是根,变成了1/(d[fa]-1)

所以,后面乘了一个d[fa]/(d[fa]-1),就变成了概率为1/(d[fa]-1)的情况。

再加上一个len[fa],就是如果走到fa的贡献了。当然还要有一个概率1/d[x]

后半部分向下走的:

E[x]/P[x],把从x出发的概率变成1,由于现在到每一个儿子的概率不是1/(d[x]-1)了,可以往上走,就变成了1/d[x]

也要调整一下。

就可以换根啦!

基环树:

  环比较麻烦。从下面的树往上走不好考虑。

  所以先处理环。

用一个栈dfs3找到所有的环上的点。是环上的点,记录进huan,共tot个。rac[i]=1,表示i是环上的点。

然后从这些环上点暴力dp,20n也不会TLE,找到ans[huan[i]]

环上暴力dp进入wrk函数。

钦定出发点st不能访问。发现,要么往左环上走,要么往右环上走,要么往下面的树走。

往树走直接dfs1即可。

往环走,发现,不经过st的情况下,也是遍历一个树诶!!!,只不过是“横躺”了环上的一部分

所以仍然可以dfs1处理。

然后,再对每一个环的每一个子树一遍dfs1,就得到了从这个子树的根(环点的一个儿子),往下走的E[x]了。

然后,对于每一个环上节点,分别往下换根。开始的时候,fa就是环上节点。

这是dfs4(其实和dfs2差不多)

换根的转移方程类似了。(不过,代码中是exp,传进来的时候其实就是ans[fa])

两个值得注意的细节:

1.dfs3找环的时候,第一次vis[y]就fl=true之后vis[y]都不可能再是环了。(可能不是正经的找基环的方法)

2.dfs1的时候,为了确定儿子的选择方法,可以暴力算一下,方便之后的转移概率处理。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=100000+5;
int n,m;
struct node{
    int nxt,to,val;
}e[2*N];
int hd[N],cnt;
double E[N],P[N];
double ans[N];
double op;
int d[N];
void add(int x,int y,int z){
    e[++cnt].nxt=hd[x];
    e[cnt].to=y;
    e[cnt].val=z;
    hd[x]=cnt;
}
bool vis[N];
int rt;
void dfs1(int x,double to,int fa,int dis){//算子树期望 ,to是到这个点的概率,dis其实没用 
    E[x]=0.00;
    P[x]=to;
    double lv=0.0;
    int can=0;
    for(int i=hd[x];i;i=e[i].nxt){//注意这里,先暴力算一下能走几个儿子,避免概率算错。 
        int y=e[i].to;
        if(y==fa) continue;
        if(vis[y]) continue;
        can++;
    }
    if(can!=0) lv=1.00/((double)can);//走每个儿子的概率,不要除以0 

    for(int i=hd[x];i;i=e[i].nxt){
        int y=e[i].to;
        if(y==fa) continue;
        if(vis[y]) continue;
        dfs1(y,to*lv,x,dis+e[i].val);
        E[x]+=P[y]*(double)e[i].val+E[y];//注意,P[y]不要再乘E[y]了,传进去的时候,to*lv相当于已经乘过了 
    }
}
void dfs2(int x,double exp,int fa,int val){
    if(x!=1){//麻烦的换根方程式,注意不要除以0 
        if(d[fa]!=1) exp=((double)val+(exp-(E[x]/P[x]+(double)val)*(1.00/(double)d[fa]))*((double)d[fa]/((double)d[fa]-1.00)))*(1.00/(double)d[x]);
        else exp=(double)val*(1.00/(double)d[x]);
        exp+=((double)E[x]/(double)P[x])*(((double)d[x]-1.00)/((double) d[x]));
        ans[x]=exp;
    }
    for(int i=hd[x];i;i=e[i].nxt){
        int y=e[i].to;
        if(y==fa) continue;
        dfs2(y,exp,x,e[i].val);
    }
}
int rac[N];
int huan[N],tot;
int sta[N],top;
bool fl=false;
void dfs3(int x,int fa){
    sta[++top]=x;
    vis[x]=1;
    for(int i=hd[x];i;i=e[i].nxt){
        int y=e[i].to;
        if(y==fa) continue;
        if(vis[y]){
            if(fl) continue;
            fl=true;//注意这个fl,保证第一次找到vis的情况(也就是环),就不会再进行了,因为回溯的时候,会再vis[y]==1一次 
            int z;
            do{
                z=sta[top];
                rac[z]=1;
                huan[++tot]=z;
                top--;
            }while(z!=y);
        }
        else dfs3(y,x);
    }
    if(sta[top]==x) top--;
}
void dfs4(int x,double exp,int fa,int val){//类似的基环树换根 
    if(d[fa]!=1) exp=((double)val+(exp-(E[x]/P[x]+(double)val)*(1.00/(double)d[fa]))*((double)d[fa]/((double)d[fa]-1.00)))*(1.00/(double)d[x]);
    else exp=(double)val*(1.00/(double)d[x]);
    exp+=((double)E[x]/(double)P[x])*(((double)d[x]-1.00)/((double) d[x]));
    ans[x]=exp;
    for(int i=hd[x];i;i=e[i].nxt){
        int y=e[i].to;
        if(y==fa) continue;
        dfs4(y,ans[x],x,e[i].val);
    }
}
double wrk(int st){//计算基环树环点的ans 
    memset(E,0,sizeof E);
    vis[st]=1;
    double ret=0.0;
    rt=0;
    if(rac[st]){
        for(int i=hd[st];i;i=e[i].nxt){
            int y=e[i].to;
            if(rac[y]){
                dfs1(y,1.00/(double)d[st],st,e[i].val);
                ret+=P[y]*e[i].val+E[y];
            }
            else{
                dfs1(y,1.00/(double)d[st],st,e[i].val);
                ret+=P[y]*e[i].val+E[y];
            }
        }       
    }
    vis[st]=0;
    return ret;
}
int main()
{
    scanf("%d%d",&n,&m);int x,y,z;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);add(y,x,z);
        d[x]++,d[y]++;
    }
    if(m==n-1){//是树 
        rt=1;
        dfs1(1,1.00,0,0);
        ans[1]=E[1];
        dfs2(1,E[1],0,0);
        op=0;
        for(int i=1;i<=n;i++){
            op+=(1.00/(double)n)*ans[i];
        }
        printf("%.5lf",op);
        return 0;
    }
    else{//是基环树 
        dfs3(1,0);  
        memset(vis,0,sizeof vis);

        for(int i=1;i<=tot;i++){
            ans[huan[i]]=wrk(huan[i]);
        }
        memset(vis,0,sizeof vis);
        for(int j=1;j<=tot;j++){
            int x=huan[j];
            vis[x]=1;
            for(int i=hd[x];i;i=e[i].nxt){
                int y=e[i].to;
                if(rac[y]) continue;
                dfs1(y,1.00,x,0);
            }
        }

        for(int j=1;j<=tot;j++){
            int x=huan[j];
            vis[x]=1;
            for(int i=hd[x];i;i=e[i].nxt){
                int y=e[i].to;
                if(rac[y]) continue;
                dfs4(y,ans[x],x,e[i].val);
            }
        }

        for(int i=1;i<=n;i++){
            op+=(1.00/(double)n)*ans[i];
        }
        printf("%.5lf",op);
        return 0;
    }   
}