题解：P9428 [蓝桥杯 2023 国 B] 逃跑

wwt100127 · 2025-03-30 17:32:15 · 题解

题目注意

尝试后跳板不再视为跳板。

思路

首先，要求任意一个出发的期望，其实也就是求从每个点出发，最短时间期望的平均值。

不妨设 dp_i 表示起点为 i 的最短时间期望，Fail_i 表示 i 为起点，跳失败的概率。

分成三种情况：

• 如果 i=1，则 Fail_i = 1,dp_i = 0。
• 如果 father_i 是“跳板”，显然不跳是较优的，这里和后面的点失败的概率也会增加，则 Fail_i = Fail_{father_i} \times P,dp_i = dp_{father_i} + 1。
• 如果 father_i 不是“跳板”，显然跳较优，那么从 i 跳成功了和从 father_i 跳成功是一样的，不成功则转化为 dp_{father_i}，则 Fail_i = Fail_{father_i},dp_i = dp_{father_i} + Fail_i。

目前最优解的代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m;
double P;
bool Jump[N];

namespace Graph
{
    int head[N],tot_edge;
    struct edge
    {
        int v,next;
    }e[N<<1];
    void G_init()
    {
        memset(head,-1,sizeof(head));
        tot_edge=-1;
    }
    void add(int u,int v)
    {
        e[++tot_edge]=(edge){v,head[u]};
        head[u]=tot_edge;
    }
    void add_edge(int u,int v)
    {
        add(u,v),add(v,u);
    }
} using namespace Graph;

double dp[N];
double Fail[N];
void dfs(int x,int fa)
{
    int i;
    for(i=head[x];~i;i=e[i].next)
    {
        int y=e[i].v;
        if(y==fa)
        continue;
        if(Jump[x]==0) dp[y]=dp[x]+(Fail[y]=Fail[x]);
        else Fail[y]=Fail[x]*P,dp[y]=dp[x]+1;
        dfs(y,x);
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int i,u,v;
    cin>>n>>m>>P;
    G_init();
    for(i=1;i<=n-1;i++)
    {
        cin>>u>>v;
        add_edge(u,v);
    }
    for(i=1;i<=m;i++)
    {
        cin>>u;
        Jump[u]=1;
    }
    Fail[1]=1;
    dfs(1,0);

    double ans=0; for(i=1;i<=n;i++) ans+=dp[i];
    cout<<fixed<<setprecision(2)<<(ans/n)<<'\n';
    return 0;
}