HDU4035 Maze

Maze

给⼀棵 \(n\) 个点的树，从节点 \(1\) 开始，每个时间点，若他在点 \(i\)，则他有 \(k_i\) 的概率回到 \(1\) 号点，有 \(e_i\) 的概率结束⾏程，有\(1-k_i-e_i\) 的概率在相邻点中等概率随机选⼀个⾛过去。

问期望⾏程时间。

\(T ≤ 30,2 ≤ N ≤ 10000\)。

题解

主元法。将节点 \(1\) 的期望设成未知变量，然后就可以用树上高消的方式从叶子推到跟，最后解个方程即可。

时间复杂度 O(n)。

CO LD eps=1e-9;
CO int N=10000+10;
vector<int> to[N];
LD ki[N],es[N];
LD c[N][3];

void dfs(int u,int fa){
    c[u][0]=0,c[u][1]=ki[u],c[u][2]=1-ki[u]-es[u];
    LD prob=(1-ki[u]-es[u])/to[u].size(),self=1;
    for(int i=0;i<(int)to[u].size();++i){
        int v=to[u][i];
        if(v==fa){
            c[u][0]=prob;
            continue;
        }
        dfs(v,u);
        self-=prob*c[v][0],c[u][1]+=prob*c[v][1],c[u][2]+=prob*c[v][2];
    }
    c[u][0]/=self,c[u][1]/=self,c[u][2]/=self;
}
void real_main(int cas){
    int n=read<int>();
    for(int i=1;i<=n;++i) to[i].clear();
    for(int i=1;i<n;++i){
        int u=read<int>(),v=read<int>();
        to[u].push_back(v),to[v].push_back(u);
    }
    for(int i=1;i<=n;++i){
        read(ki[i]),read(es[i]);
        ki[i]/=100,es[i]/=100;
    }
    dfs(1,0);
    printf("Case %d: ",cas);
    if(1-c[1][1]<eps) puts("impossible");
    else printf("%.9lf\n",c[1][2]/(1-c[1][1]));
}
int main(){
    int T=read<int>();
    for(int i=1;i<=T;++i) real_main(i);
    return 0;
}