P2081 [NOI2012] 迷失游乐园——期望+换根dp+基环树

· · 个人记录

第二道独立切掉的有一点思维含量的紫题
好开心好开心

50pts

初见没思路，考虑部分分

注意到，因为不会走走过的路，所以走到不能再走 在树形结构上体现 为走到叶子节点的距离

满足无后效性，那么就可以考虑dp(先设1为根)

设 dp_u 为在 u 节点时向下所能走的期望距离

考虑转移， dp_u 由它的每一个子节点转移过来，具体转移就是带上边权乘概率加起来，状态转移方程为

dp_u=\sum_{v=son_u}\big(dp_v+dis(u,v)\big)\times p_{u,v} 根据题意，每项的概率都是相等的，于是就可以把 $p_{u,v}$ 提出来最后再除 但是这个dp**只能正确求出根节点的答案**，从其他结点开始的话除了可以向下走还可以向上走 于是做完第一次dp之后又要做一次换根dp 把之前的dp结果记作dp1，考虑从一个节点换到另一个节点 稍微一画图，可以看出构成其答案的部分为**其的子树加上相对于整棵树的补集** 相对于整棵树的补集可以从父亲的dp值转移得来，子树就直接从第一次的dp来 转移的时候，需要在父亲的dp值中**去掉属于自己期望的那部分**，再在补集整体加上到父亲的边权 $w$ (注意此时各部分的概率改变了，**期望整体要重算**，所以这里建议前面算出的可以先不要除，等到最后贡献答案的时候再除) 于是换根dp的方程就可以描述为（此时dp,dp1均没有除,dp2是除过的dp1,ccnt是儿子数量） $$dp_u=(dp1_u+\frac{(dp_{fa}-dp2_u-w)}{ccnt_{fa}}+w)$$ 根节点的儿子要另外讨论，分母部分要多减1(因为不能往父亲走了) 于是就可以拿到 $50pts$ 了，时间复杂度 $O(n)

100pts

是的我不会基环树

听说套路有割边和分类讨论，试了下割边，似乎会重复

所以考虑环内环外分开讨论（本来还在想缩点）

对于环外

可以发现只要跑到了环外就不会回到环内了

这个时候直接针对环上的每一个点所在子树进行上述第一次dp

因为 以环外的节点为起点时 可以跑到环内，先不考虑环外的换根dp

对于环内

注意到环上节点的数量很少，可以暴力

考虑对于每一个环上的节点为开始在环上跑，每跑到一个节点就考虑两种决策

于是就可以整个类似搜索的东西，不过事实上复杂度只有 O(size^2) ， size 为环的大小

再回到环外

这下就要继续考虑换根dp了（这个时候似乎不太严谨），结果想了半天发现和 50pts 的一样……

AC Code:

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

const int MAXN=1e5+5;

struct EDGE{
    int to,w;
};

int fa[MAXN],ccnt[MAXN],val[MAXN];
vector<EDGE > edge[MAXN];
int n,m;
db dp1[MAXN],dp2[MAXN],dp[MAXN],ans=0.0;//第一遍dp算子树期望(没除)，第二遍换根dp 

db dfs1(int u){
    dp1[u]=0.0;
    for(auto v:edge[u]){
        if(v.to==fa[u]) continue;
        ++ccnt[u];fa[v.to]=u;val[v.to]=v.w;
        dp1[u]+=dfs1(v.to)+v.w;
    }
    dp2[u]=dp1[u];
    if(ccnt[u]==0) return dp1[u];
    dp2[u]=dp1[u]/ccnt[u];
//  printf("[%d]:%lf\n",u,dp1[u]);
    return dp2[u];
}//

void dfs2(int u,int root){
    dp[u]=dp1[u];
    if(u==root){
        ans+=dp[u]/ccnt[u];
//      printf("[%d]:%lf\n",u,dp[u]/ccnt[u]);
        for(auto v:edge[u]){
            if(v.to==fa[u]) continue;
            dfs2(v.to,root);
        }
        return ;
    }
    if(fa[u]==root){
        if(ccnt[fa[u]]==1) dp[u]+=(dp[fa[u]]-dp2[u]-val[u])+val[u];
        else dp[u]+=(dp[fa[u]]-dp2[u]-val[u])/(ccnt[fa[u]]-1)+val[u];
        ans+=dp[u]/(ccnt[u]+1);
//      printf("[%d]:%lf,%lf,%d\n",u,dp[u]/(ccnt[u]+1),dp[u],ccnt[u]+1);
        for(auto v:edge[u]){
            if(v.to==fa[u]) continue;
            dfs2(v.to,root);
        }
        return ;
    }
    dp[u]+=(dp[fa[u]]-dp2[u]-val[u])/ccnt[fa[u]]+val[u];
    ans+=dp[u]/(ccnt[u]+1);
//  printf("[%d]:%lf\n",u,dp[u]/(ccnt[u]+1));
    for(auto v:edge[u]){
        if(v.to==fa[u]) continue;
        dfs2(v.to,root);
    }
}//

bool vis[MAXN],inring[MAXN];
int stk[MAXN],top=0;bool k=0;

void findring(int u,int fa){
    vis[u]=1;stk[++top]=u;
    for(auto v:edge[u]){
        if(k) return ;
        if(v.to==fa) continue;
        if(vis[v.to]){
            while(stk[top]!=v.to)
                inring[stk[top--]]=1;
            inring[stk[top--]]=1;
            k=1;
            break;
        }findring(v.to,u);
    }
}//

db ringdfs1(int u){
    dp1[u]=0.0;
    for(auto v:edge[u]){
        if(v.to==fa[u])  continue;
        if(inring[v.to]) continue;
        ++ccnt[u];fa[v.to]=u;val[v.to]=v.w;
        dp1[u]+=ringdfs1(v.to)+v.w;
    }
    dp2[u]=dp1[u];
    if(ccnt[u]==0) return dp1[u];
    dp2[u]=dp1[u]/ccnt[u];
//  printf("[%d]:%lf\n",u,dp1[u]);
    return dp2[u];
}//

db rE[MAXN];//考虑了环之后的期望(没除) 

db ringdp(int u,int beg){
    db res=dp1[u];vis[u]=1;
    int cnt=0;
    for(auto v:edge[u]){
        if(!inring[v.to]) continue;
        if(vis[v.to]) continue;//不走回头路 
        res+=ringdp(v.to,beg)+v.w;
        ++cnt;
    }
    vis[u]=0;
//  printf("[%d,%d],%lf,%lf\n",u,beg,res,res/(cnt+ccnt[u]));
    if(u==beg) rE[beg]=res;
    if(cnt+ccnt[u]==0) return 0.0;
    return res/(cnt+ccnt[u]);
}//

void rdfs2(int u,int root){
    dp[u]=dp1[u];
    if(u==root){
        dp[u]=rE[u];//环上的点 
        for(auto v:edge[u]){
            if(inring[v.to]) continue;
            if(v.to==fa[u]) continue;
            rdfs2(v.to,root);
        }
        return ;
    }
    if(fa[u]==root){
        dp[u]+=(dp[fa[u]]-dp2[u]-val[u])/(ccnt[fa[u]]+1)+val[u];
        ans+=dp[u]/(ccnt[u]+1);
//      printf("[%d]:%lf,%lf,%d\n",u,dp[u]/(ccnt[u]+1),dp[u],ccnt[u]+1);
        for(auto v:edge[u]){
            if(inring[v.to]) continue;
            if(v.to==fa[u]) continue;
            rdfs2(v.to,root);
        }
        return ;
    }
    dp[u]+=(dp[fa[u]]-dp2[u]-val[u])/ccnt[fa[u]]+val[u];
    ans+=dp[u]/(ccnt[u]+1);
//  printf("[%d]:%lf\n",u,dp[u]/(ccnt[u]+1));
    for(auto v:edge[u]){
        if(inring[v.to]) continue;
        if(v.to==fa[u]) continue;
        rdfs2(v.to,root);
    }
}//

void work(){
    scanf("%d%d",&n,&m);
    int u,v,w;
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&u,&v,&w);
        edge[u].push_back(EDGE{v,w});
        edge[v].push_back(EDGE{u,w});
    }
    if(m==n-1){
        dfs1(1);
        dfs2(1,1);
        printf("%.05lf",ans/n);
        return ;
    }
    //接下来是基环树
    findring(1,1);

    for(int i=1;i<=n;++i)
        if(inring[i])
            ringdfs1(i);

    memset(vis,0,sizeof(vis));

    for(int i=1;i<=n;++i)
        if(inring[i]){
            ans+=ringdp(i,i);
//          printf("|%d|,ans=%lf\n",i,ans);
        }

//  for(int i=1;i<=n;++i)
//      if(inring[i])
//          printf("[%d],%lf\n",i,rE[i]);

    for(int i=1;i<=n;++i)
        if(inring[i])
            rdfs2(i,i);

    printf("%.05lf\n",ans/n);
}

int main(){
    work();
    return 0;
}