[CERC2017]Gambling Guide

小鱼儿 2023-10-11 05:26 39阅读 0赞

[题目][Link 1]

看起来非常随机游走，但是由于我们可以停在原地，所以变得不是非常一样

设\\(f\_x\\)表示从\\(x\\)到\\(n\\)的期望距离

如果我们提前知道了\\(f\\)，那么我们随机到了一张到\\(y\\)的车票，发现\\(f\_y>f\_x\\)，那么我们不如停在原地再随一张

所以就有

\\\[f\_x=\\frac\{\\sum\_\{(x,y)\\in e\}1+\\min(f\_x,f\_y)\}\{d\_x\}=1+\\frac\{\\sum\_\{(x,y)\\in e\}\\min(f\_x,f\_y)\}\{d\_x\}\\\]

这个式子不是很好看，我们将其改写一下

\\\[f\_x=1+\\frac\{\\sum\_\{(x,y)\\in e\}\[f\_y<f\_x\]f\_y+f\_x(d-\\sum\_\{(x,y)\\in e\}\[f\_y<f\_x\])\}\{d\_x\}=\\frac\{d\_x+\\sum\_\{(x,y)\\in e\}\[f\_y<f\_x\]f\_y\}\{\\sum\_\{(x,y)\\in e\}\[f\_y<f\_x\]\}\\\]

根据这个式子只有比较小的\\(f\_y\\)才能去更新\\(f\_x\\)，于是我们做一个类似于\\(\\rm Dijkstra\\)的过程，每次从堆顶取出最小的\\(f\_y\\)去更新即可

代码

#include<bits/stdc++.h>
    #define re register
    #define mp std::make_pair
    inline int read() {
        char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
        while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
    }
    const int maxn=3e5+5;
    typedef std::pair<double,int> pii;
    std::priority_queue<pii,std::vector<pii>,std::greater<pii> > q;
    struct E{int v,nxt;}e[maxn<<1];
    int n,num,m;
    double dis[maxn],s[maxn],p[maxn];
    int du[maxn],head[maxn],vis[maxn];
    inline void add(int x,int y) {e[++num].v=y;e[num].nxt=head[x];head[x]=num;}
    int main() {
        n=read(),m=read();
        for(re int x,y,i=1;i<=m;i++)    
            x=read(),y=read(),du[x]++,du[y]++,add(x,y),add(y,x);
        dis[n]=0,q.push(mp(dis[n],n));
        while(!q.empty()) {
            int k=q.top().second;q.pop();
            if(vis[k]) continue;vis[k]=1;
            for(re int i=head[k];i;i=e[i].nxt) {
                if(vis[e[i].v]) continue;
                p[e[i].v]+=1;s[e[i].v]+=dis[k];
                dis[e[i].v]=(du[e[i].v]+s[e[i].v])/p[e[i].v];
                q.push(mp(dis[e[i].v],e[i].v));
            }
        }
        printf("%.10lf\n",dis[1]);
        return 0;
    }

转载于:https://www.cnblogs.com/asuldb/p/11567552.html

[Link 1]: https://www.luogu.org/problem/P4745