M_sea

洛谷4745 [CERC2017]Gambling Guide
Luogu分析设 $f[x]$ 表示从 $x$ 走到 $n$ 的期望步数。显然有 $\large f[u] = \...
扫描右侧二维码阅读全文
12
2019/04

洛谷4745 [CERC2017]Gambling Guide

Luogu

分析

设 $f[x]$ 表示从 $x$ 走到 $n$ 的期望步数。

显然有 $\large f[u] = \frac{\sum\limits_{(u,v)\in E}\min(f[u] , f[v])}{deg[u]} + 1$ 。

显然,如果 $f[v]<f[u]$ 就会有贡献,于是可以跑 $\mathrm{dijkstra}$ 。

但是这样子不太好算。把式子变形一下,变为 $\large f[u]= \frac{deg[u] + \sum\limits_{(u,v) \in E} \big[f[v]<f[u]\big]f[v]}{\sum\limits_{(u,v) \in E} \big[f[v] < f[u]\big]}$ 。这样子就可以在 $\mathrm{dijkstra}$ 时直接算出 $f$ 了。

至于正确性?意会一下即可 可以看 神仙 $\mathrm{\color{black}{p}\color{red}{sj}}$ 的 $\mathrm{blog}$

具体实现和细节见代码。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=300000+10;

int n,m;
int deg[N],cnt[N],vis[N];
double f[N],s[N];
struct Edge { int v,nxt; } e[N<<1];
int head[N];

inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(Edge){v,head[u]},head[u]=cnt;
}

struct node { int u; double d; };
bool operator <(node a,node b) { return a.d<b.d; }
bool operator >(node a,node b) { return b<a; }

inline void dijkstra() {
    priority_queue<node,vector<node>,greater<node> > Q;
    memset(f,127,sizeof(f));
    Q.push((node){n,0}),f[n]=0;
    while (!Q.empty()) {
        node x=Q.top(); Q.pop();
        int u=x.u; if (vis[u]) continue;
        vis[u]=1;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v; if (vis[v]) continue;
            ++cnt[v],s[v]+=f[u],f[v]=(s[v]+deg[v])/cnt[v];
            Q.push((node){v,f[v]});
        }
    }
}

int main() {
    n=read(),m=read();
    for (re int i=1;i<=m;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
        ++deg[u],++deg[v];
    }
    dijkstra(); printf("%.10lf\n",f[1]);
    return 0;
}
最后修改:2019 年 05 月 26 日 09 : 37 PM

发表评论