BZOJ5197【CERC2017】Gambling Guide <概率DP+Dijkstra>

Posted on Symbols count in article: 1.1k Reading time ≈ 4 mins.

Problem

【CERC2017】Gambling Guide

Time  Limit:  20  Sec\mathrm{Time\;Limit:\;20\;Sec}
Memory  Limit:  512  MB\mathrm{Memory\;Limit:\;512\;MB}
Special  Judge\mathrm{Special\;Judge}

Description

给定一张nn个点，mm条双向边的无向图。
你要从11号点走到nn号点。当你位于xx点时，你需要花11元钱，等概率随机地买到与xx相邻的一个点的票，只有通过票才能走到其它点。
每当完成一次交易时，你可以选择直接使用那张票，也可以选择扔掉那张票然后再花11元钱随机买另一张票。注意你可以无限次扔票。
请使用最佳的策略，使得期望花的钱数最少。

Input

第一行包含两个正整数n,mn,m (1≤n,m≤3×105)(1\le n,m\le3\times10^5)，表示点数和边数。
接下来mm行，每行两个正整数u,vu,v (1≤u,v≤n)(1\le u,v\le n)，表示一条双向边。
输入数据保证无重边、无自环，且11号点一定可以走到nn号点。

Output

输出一行一个实数，即最少的期望花费，当绝对或者相对误差不超过10−610^{-6}时视为正确。

Sample Input

1
2
3
4
5
6
7
8
9
5 8
1 2
1 3
1 4
2 3
2 4
3 5
5 4
2 5

Sample Output

1
4.1111111111

标签：概率DP Dijkstra

Solution

好题，精妙的DP\mathrm{DP}转移。

原题意相当于从11走到nn，每步可以随机一个相邻的点，选择走或不走，求期望步数。

令f(x)f(x)为从xx到nn的期望步数。如果随出来的相邻点为yy，且f(y)>f(x)f(y)>f(x)，那么肯定不走最优；否则一定走到yy更优。令xx的出边走向的点集为TT，有f(x)=∑y∈Tmin⁡(f(x),f(y))deg(x)f(x)=\sum_{y\in T}\frac{\min(f(x),f(y))}{deg(x)}。

考虑以何种顺序进行这个DP\mathrm{DP}。最开始时，只有f(n)=0f(n)=0，这个值是确定的，于是我们将nn加入到一个集合{S}\lbrace S\rbrace中。集合{S}\lbrace S\rbrace为现在“固定(fixed)”了的点的集合，在SS中的点的ff值一定比没在其中的点的ff值小。考虑用SS中固定了的ff值去更新相邻的点，对于这些未被“固定”的相邻的点，如果其走向已经被”固定“的点，那么一定更优；否则，一定没有留在当前点优。
那么有

f(x)=1+∑neighbour  y∈Sf(y)deg(x)+∑neighbour  y∉Sf(x)deg(x)f(x)=1+\sum_{\mathrm{neighbour}\;y\in S}\frac{f(y)}{deg(x)}+\sum_{\mathrm{neighbour}\;y\notin S}\frac{f(x)}{deg(x)}

移项化简得

f(x)=deg(x)+∑neighbour  y∈Sf(y)deg(x)−∑neighbour  y∉S1f(x)=\frac{deg(x)+\sum_{\mathrm{neighbour}\;y\in S}f(y)}{deg(x)-\sum_{\mathrm{neighbour}\;y\notin S}1}

由于在SS中的点ff值一定比外面的小，已经被”固定“的点不可能因为走向没被”固定“的点而变得更优，所以一个点一旦固定了，它的ff值一定固定了，我们用它去更新其他的点。每次操作时，我们选出没被固定的点中ff值最小的点（因为这个值不可能再被其他没被固定的点更新了），然后用它更新周围的点。

我们发现这个过程和Dijkstra\mathrm{Dijkstra}单源最短路极为相似，都是每次固定一个距离最小的点，更新其周围的点。和Dijkstra\mathrm{Dijkstra}一样，我们可以用堆来优化找ff最小的未被固定的点的过程。这样总时间复杂度O((N+M)log⁡N)O((N+M)\log{N})。

附上官方题解

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
#define fir first
#define sec second
#define MAX_N 300000
#define INF 0x3f3f3f3f
using namespace std;
typedef double dnt;
typedef pair<dnt,int> pdi;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, sz;
dnt d[MAX_N+5], f[MAX_N+5];
dnt p[MAX_N+5], q[MAX_N+5];
int pr[MAX_N+5]; bool mrk[MAX_N+5];
struct edge {int v, nxt;} E[MAX_N<<1];
void insert(int u, int v) {E[sz] = (edge){v, pr[u]}, pr[u] = sz++;}
void addedge(int u, int v) {insert(u, v), insert(v, u), d[u]++, d[v]++;}
dnt Dijkstra() {
    priority_queue <pdi> heap;
    heap.push(pdi((f[n] = 0), n));
    while (!heap.empty()) {
        int u = heap.top().sec; heap.pop();
        if (mrk[u]) continue; mrk[u] = true;
        for (int i = pr[u], v; ~i; i = E[i].nxt) if (!mrk[v = E[i].v])
            f[v] = ((p[v] += f[u])+d[v])/(++q[v]), heap.push(pdi(-f[v], v));
    }
    return f[1];
}
int main() {
    read(n), read(m);
    memset(pr, -1, sizeof pr);
    for (int i = 1, u, v; i <= m; i++)
        read(u), read(v), addedge(u, v);
    return printf("%lf\n", Dijkstra()), 0;
}