P2081 [NOI2012] 迷失游乐园

Vision271 · 2022-05-11 18:46:04 · 个人记录

题意

• 给定一个 n 点，m 边的边带权的无向无根基环树。

• 求\dfrac {\sum\limits_{i=1}^{n} E(len_i)}{n}，其中 E(len_i) 为从 i 出发的路径长度的期望（可以认为岔路口均匀随机）。

数据范围

• 无重边。似乎无自环。

• 环上点个数 cnt\leqslant 20。

解析

• 首先考虑一个常规树上的解法：

• 记从 i 出发的期望长度为 dp_i，按照一般的假换根 DP 的思路，考虑向上走/向下走的期望长度分别为 up_i,dw_i。

• 定义 sons_i,fas_i 分别为 i 的直接儿子/父亲的数量（之所以 fas_i 没有直接按 1 算是为了后面的基环树做法）。

• 那么我们有:

• up_i=dis_{i,fa}+\dfrac{up_{fa}\times fas_{fa} + dw_{fa}\times sons_{fa}-dis_{i,fa}-dw_i}{deg_{fa}-1}

• 到这里都非常显然。我贴一个阶段性代码（推导性注释已删去,调试代码已删去,仅保留了少量的解释性注释）。到这里我们就可以拿到 50 分。

const int maxn=1e5+7;
int n,m,u,v,l[maxn],son[maxn];
struct bian{
    int to,l;
    bian(){}
    bian(int _to,int _l){
        to=_to,l=_l;
    }
};
b_s<bian> e[maxn];

double dw[maxn];
void dfd(int x,int fa){
    for(bian a:e[x])
        if(a.to!=fa)
            ++son[x],dfd(a.to,x);
    for(bian a:e[x])
        if(a.to!=fa)
            dw[x]+=1.0*a.l+dw[a.to];
    if(son[x]) dw[x]/=1.0*son[x];
    return;
}

double up[maxn];
void dfu(int x,int fa){//注意一下，为了方便，我们在dfu中是站在父亲那里处理儿子 
    for(bian a:e[x])
        if(a.to!=fa){
            if(x==1){
                up[a.to]=dw[x]*son[x]-a.l-dw[a.to];
                if(son[fa]>1) up[a.to]/=(son[x]-1);
                up[a.to]+=1.0*a.l;
            }
            else
                up[a.to]=1.0*a.l+(up[x]+dw[x]*son[x]-a.l-dw[a.to])/son[x];
        }
    for(bian a:e[x])
        if(a.to!=fa)
            dfu(a.to,x);
    return;
}

double dp[maxn],ans;

int main(){
    n=rd(),m=rd();
    For(i,1,m){
        u=rd(),v=rd(),l[i]=rd();
        e[u]+=bian(v,l[i]),e[v]+=bian(u,l[i]);
    }
    dfd(1,1);//咱们就规定1是FA
    dfu(1,1);
    dp[1]=dw[1];
    For(i,2,n)
        dp[i]=(up[i]+dw[i]*son[i])/(son[i]+1);
    For(i,1,n) ans+=dp[i];
    ans/=1.0*n;
    printf("%.5lf",ans);
    return 0;
}

• 下面尝试着把上面的策略推广到基环树情况。

• 我们的 up_i,dw_i 是为了求 dp_i 而设计的，其中 dw 自下而上，up 自上而下。

• 考虑到环非常小,也许可以在思路上把环上点合起来作为一个虚点。为了避免它造成很麻烦的影响，考虑把它作为根。

• 那么我们现在定义 dw 是朝着环外走，up 是朝着环上走。

• 所以环上点的 up 直接暴力。具体来讲，考虑到它走到每个环上点的概率,将它继续在环上/下去的贡献分别加权计算。不允许又回到自己这点。这样就只依赖 dw。

  • 9.29 upd：这种做法非常特殊而优美，非常依赖本题的性质（同一个点不许访问两次）。可以参看海洋馆那道题...事实上，暴力部分最毒瘤。

• 然后的话，非环点的 up 就易得了。

• 下面给出示范代码（处理常规树的思路是将它转为一个环里只有"1"的基环树）。

#include<bits/stdc++.h>
#define ll long long
#define us unsigned
#define b_s basic_string
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define foR(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
ll rd(){
    ll s=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)){s=(s<<3)+(s<<1)+(ch^48);if(ch!='\n') ch=getchar();}
    return s*f;
}
char wtst[66];
int wtps;
void wt(ll x){
    if(x<0) putchar('-'),x=-x;
    while(x>9) wtst[++wtps]=(x%10+'0'),x/=10;
    wtst[++wtps]=x+'0';
    while(wtps) putchar(wtst[wtps--]);
    return;
}
void wth(ll x){wt(x);putchar('\n');return;}
void wtk(ll x){wt(x);putchar(' ');return;}

const int maxn=1e5+7;
int n,m,u,v,l[maxn],son[maxn];
struct bian{
    int to,l;
    bian(){}
    bian(int _to,int _l){
        to=_to,l=_l;
    }
};
b_s<bian> e[maxn];

int prest[maxn],p,vis[maxn],cir[27],cnt;
bool flag,incir[maxn];
void predfs(int x,int fa){
    if(flag) return;
    prest[++p]=x;vis[x]=1;
    for(bian a:e[x]){
        if(a.to==fa) continue;
        if(vis[a.to]==0) predfs(a.to,x);
        else{
            flag=1;
            while(true){
                cir[++cnt]=prest[p];
                vis[prest[p]]=0,incir[prest[p]]=1;
                --p;
                if(prest[p+1]==a.to) return;
            }
        }
    }
    --p;vis[x]=0;
    return;
}

double dw[maxn];
void dfd(int x,int fa){
    for(bian a:e[x])
        if(a.to!=fa && !(incir[a.to] && incir[x]))//不允许从环上一点扩展到环上另一点(计算dw的时候可认为环上的所有边都不存在) 
            ++son[x],dfd(a.to,x);
    for(bian a:e[x])
        if(a.to!=fa && !(incir[a.to] && incir[x]))
            dw[x]+=1.0*a.l+dw[a.to];
    if(son[x]) dw[x]/=1.0*son[x];
    return;
}

double up[maxn];

double dff(int x,int fa,int FA){
    double ret=son[x]*dw[x];
    int chu=son[x];
    if(x==FA) ret=0.0,chu=0;
    for(bian a:e[x])
        if(a.to!=fa && a.to!=FA && incir[a.to] && incir[x])//从当前点走到另一个环上点,不允许回到起点 
            ++chu,ret+=dff(a.to,x,FA)+a.l;
    if(chu!=0) ret=ret/chu;
    return ret;
}

void dfu(int x,int fa){//注意一下，为了方便，我们在dfu中是站在父亲那里处理儿子 
    for(bian a:e[x])
        if(a.to!=fa && !(incir[a.to] && incir[x])){
            if(incir[x]){
                if(cnt==1 && x==1){//假基环树,这个是根节点1
                    up[a.to]=dw[x]*son[x]-a.l-dw[a.to];
                    if(son[fa]>1) up[a.to]/=(son[x]-1);
                    up[a.to]+=1.0*a.l;
                } 
                else up[a.to]=1.0*a.l+(2*up[x]+dw[x]*son[x]-a.l-dw[a.to])/(son[x]+1);
            }
            else
                up[a.to]=1.0*a.l+(up[x]+dw[x]*son[x]-a.l-dw[a.to])/son[x];
        }
    for(bian a:e[x])
        if(a.to!=fa && !(incir[a.to] && incir[x]))
            dfu(a.to,x);
    return;
}

double dp[maxn],ans;

int main(){
    n=rd(),m=rd();
    For(i,1,m){
        u=rd(),v=rd(),l[i]=rd();
        e[u]+=bian(v,l[i]),e[v]+=bian(u,l[i]);
    }

    predfs(1,1);
    if(cnt==0) cnt=1,cir[1]=1,incir[1]=1;
    For(i,1,cnt) dfd(cir[i],cir[i]);//从每个环上点开始,处理好它和它子树的dw
    For(i,1,cnt) up[cir[i]]=dff(cir[i],cir[i],cir[i]);//暴力处理环上每个点的up 
    For(i,1,cnt) dfu(cir[i],cir[i]);//站在父亲处理儿子 

    For(i,1,n){ 
        if(incir[i]){
            if(cnt==1) dp[i]=dw[i];
            else dp[i]=(up[i]*2+dw[i]*son[i])/(son[i]+2);
        }
        else 
            dp[i]=(up[i]+dw[i]*son[i])/(son[i]+1);
    }
    For(i,1,n) ans+=dp[i];
    ans/=1.0*n;
    printf("%.5lf",ans);
    return 0;
}

总结与反思

1.知识点

• 一如其他树上期望 DP 一般，它又暴露出了我 tree dp 学的很烂的事实（当然，更进一步的事实是，在期望章节打了几个 tdp 之后有了长足进步）。

• 学到了 dfs 找环。

2.解题中的失误

• 做朴素解法时，up 中的下标传得不对。父亲和儿子的下标混淆了。

• 推广为基环树解法之后,没有注意到朴素树与基环树的兼容性问题。导致那份代码完全丧失了解朴素树情况的能力。

• 因为前期的式子中一直默认 fas_i=1（而事实上环上的点可以往两边走，它们的 fas_i=2），推广后的代码的转移式有严重缺陷。

3.其他

• 需要锻炼手造样例的能力。

  • 由于对自己码力的不自信和懒惰,调试本题时主要依赖着数据下载。

  • 但事实上，使用了的 1 和 6 两个数据点一个是朴素链，一个是朴素基环树（有点像小型菊花图吧,但满共 10 个点)。

  • 有理由认为这都是我应该自己手制出来的简单情形。

• 希望下次代码能写得好看一些，这份代码中的“假环”所带来的复杂判断语句并不优美。