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

Problem

【CERC2017】Gambling Guide

Description

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

Input

第一行包含两个正整数，表示点数和边数。
接下来行，每行两个正整数，表示一条双向边。
输入数据保证无重边、无自环，且号点一定可以走到号点。

Output

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

Sample Input

Sample Output

1	4.1111111111

标签：概率DP Dijkstra

Solution

好题，精妙的转移。

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

令为从到的期望步数。如果随出来的相邻点为，且，那么肯定不走最优；否则一定走到更优。令的出边走向的点集为，有。

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

移项化简得

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

我们发现这个过程和单源最短路极为相似，都是每次固定一个距离最小的点，更新其周围的点。和一样，我们可以用堆来优化找最小的未被固定的点的过程。这样总时间复杂度。

附上官方题解

Code

#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;
}