[CERC2017] Gambling Guide

Description

给定一张 $n$ 个点 $m$ 条边的无向图。当你在点 $u$ 时，你可以花费 $1$ 的费用向系统询问当前可以去哪个点，系统会从点 $u$ 的所有出边中随机选择一条告诉你。你可以选择去，或者重新花费并询问。初始时刻你在 $1$ 号点，要去 $n$ 号点。求最少花费的期望。
$1\leq n,m\leq 3\times 10^5$

Solution

设 $f_u$ 表示从 $u$ 号点到 $n$ 号点的期望最少花费，$\deg_u$ 表示 $u$ 的度数。则有转移：

$f_u=\frac{1}{\deg_u}\sum_{(u,v)\in E}\min\{f_u,f_v\} + 1$

这东西看着就不是很可做。$\min$ 的存在使得暴力高斯消元都不可行，只能另辟蹊径。

显然，当 $(x,y)\in E$ 时，若点 $y$ 对点 $x$ 有贡献，则有 $f_y<f_x$。
我们考虑 按照花费从小到大依次确定每个点的期望最少花费 。显然，第一次确定的是 $f_n=0$ 。

从当前已经确定的点集的出边走可以找到一个可到达的点集。钦定每个点 $u$ 都认为自己的 $f_u$ 是当前可以到达的但是未确定的点中最小的 $f$。假设这个虚假的 $f_u$ 为 $f'_u$ 。当前暂时不能被已经确定的点到达的点的 $f'$ 认为是 $+\infin$ 。那么对于这个题而言，有一个如下的结论：

若 $f'_u$ 是当前集合中最小的，则 $f_u=f'_u$ 。

为什么呢？

首先，假设目前可到达但未确定的点集为 $\mathcal{P}$，那么一定存在 $z\in \mathcal{P}$，满足 $f_z=f'_z$。因为集合 $\mathcal{P}$ 一定存在一个最小值。
也就是我们要找的东西一定是存在的。接下来我们考虑反证法。

假设目前对于 $u$ 号点而言，出边中有 $\text{cnt}_u$ 个点的函数值比 $u$ 小，且它们的函数值之和为 $\text{sum}_u$ （注意这些点一定是当前已确定的点）。则：

$f_u=\frac{\text{sum}_u+\deg_u}{\text{cnt}_u}$

假设 $(u,v)\in E$ ，并且 $f'_v>f'_u$ 。如果我们认为 $v$ 是当前集合 $f$ 最小的，那么 $f_v=f'_v$ ，且我们需要用 $f_v$ 更新 $f'_u$ 。注意这个更新，假设更新前的 $f'_u$ 为 $g_u$

$f'_u=\frac{\text{sum}_u+\deg_u+f'_v}{\text{cnt}_u+1}=\frac{g_u\times \text{cnt}_u+f'_v}{\text{cnt}_u+1}$

因为 $f'_v>g_u$ ，所以 $f'_u>g_u$ ，也就是变劣了。考虑 $f_u$ 最初的方程形式的转移，如果当前我们的 $\min\{f_u,f_v\}$ 取在了 $f_v$ 处会比取在 $f_u$ 处更劣，说明 $f_u<f_v$ 。也就是当前不能取 $v$ 。

那么通过上述的反证法，我们每次可以确定当前点集 $\mathcal{P}$ 中一个点的 $f$，并继续更新其余点的 $f'$ 。这个过程与 $\text{dijkstra}$ 很像，我们参照 $\text{dijkstra}$ 的实现方法即可。

复杂度 $\mathcal{O}(m\log m)$ 。

Code

const int N = 3e5 + 233;
using namespace std;
int n, m, num;
int deg[N], used[N], head[N], nt[N << 1], to[N << 1];
long double f[N], sum[N], cnt[N];
struct node{
    long double v; int x;
    node(long double v = 0, int x = 0):
        v(v), x(x) {}
    bool operator <(const node &b) const {
        return v > b.v;
    }
};
priority_queue<node>q;
void Dijkstra(){
    for(int i = 1; i <= n; ++i) 
        f[i] = 1e100, sum[i] = cnt[i] = 0;
    f[n] = 0; q.push(node(0, n));
    while(!q.empty()){
        int u = q.top().x; q.pop();
        if(used[u]) continue;
        used[u] = 1;
        for(int i = head[u]; i; i = nt[i]){
            int v = to[i]; if(used[v]) continue;
            cnt[v] += 1; sum[v] += f[u]; 
            f[v] = (deg[v] + sum[v]) / cnt[v];
            q.push(node(f[v], v));
        }
    }
}
void add(int x, int y){
    ++num, nt[num] = head[x], head[x] = num, to[num] = y; ++deg[x];
    ++num, nt[num] = head[y], head[y] = num, to[num] = x; ++deg[y];
}
int main(){

    fin >> n >> m;
    for(int i = 1, u, v; i <= m; ++i)
        fin >> u >> v, add(u, v);
    Dijkstra();
    printf("%.6Lf\n", f[1]);
    return 0;
}