题解 P4745 【[CERC2017]Gambling Guide】

· · 题解

分析

按照期望题一般的做法，我们设 f[u] 为从 u 走到终点 n 的期望花费

设 du[u] 为节点 u 的出度

那么 f[u]= \frac{\sum_{u->v} min(f[u],f[v])}{du[u]}+1

我们会发现这个式子既包含 f[u] 本身又包含与 f[u] 相邻的点 f[v]

不好直接转移

但是我们可以确定，如果 f[v]<f[u] ，那么 f[v] 一定会对 f[u] 做出贡献

因此，我们可以利用 Dij 的思想开一个小根堆，每次取出最小的来更新其它的

因为当前的值是最小的，所以一定不会有其它的点可以影响它

我们设 u 被与它相邻的点的 f 值更新了 cnt 次，这些值的和为 sum

则 f[u]=\frac{sum+(du[u]-cnt[u]) \times f[u]}{du[u]}+1

整理可得 f[u]=\frac{sum+du[u]}{cnt}

代码

#include<cstdio>
#include<cstring>
#include<queue>
const int maxn=6e5+5;
inline int read(){
    int x=0,fh=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') fh=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*fh;
}
int head[maxn],tot=1;
struct asd{
    int to,next;
}b[maxn];
void ad(int aa,int bb){
    b[tot].to=bb;
    b[tot].next=head[aa];
    head[aa]=tot++;
}
struct jie{
    int num;
    double jl;
    jie(){}
    jie(int aa,double bb){
        num=aa,jl=bb;
    }
    bool operator < (const jie &A) const{
        return jl>A.jl;
    }
};
int n,m,du[maxn],cnt[maxn];
double sum[maxn],f[maxn];
bool vis[maxn];
std::priority_queue<jie> q;
void dij(){
    q.push(jie(n,0));
    while(!q.empty()){
        int now=q.top().num;
        q.pop();
        if(vis[now]) continue;
        vis[now]=1;
        for(int i=head[now];i!=-1;i=b[i].next){
            int u=b[i].to;
            if(vis[u]) continue;
            cnt[u]++;
            sum[u]+=f[now];
            f[u]=(du[u]+sum[u])/cnt[u];
            q.push(jie(u,f[u]));
        }
    }
}
int main(){
    memset(head,-1,sizeof(head));
    n=read(),m=read();
    for(int i=1;i<=m;i++){
        int aa,bb;
        aa=read(),bb=read();
        ad(aa,bb);
        ad(bb,aa);
        du[aa]++,du[bb]++;
    }
    dij();
    printf("%.10f\n",f[1]);
    return 0;
}