题目描述
给定一张 n 个点, m 条双向边的无向图
你要从 1 号点走到 n 号点当你位于 x 点时, 你需要花 1 元钱, 等概率随机地买到与 x 相邻的一个点的票, 只有通过票才能走到其它点
每当完成一次交易时, 你可以选择直接使用那张票, 也可以选择扔掉那张票然后再花 1 元钱随机买另一张票注意你可以无限次扔票
请使用最佳的策略, 使得期望花的钱数最少
输入
第一行包含两个正整数 n,m(1<=n,m<=300000), 表示点数和边数
接下来 m 行, 每行两个正整数 u,v(1<=u,v<=n), 表示一条双向边
输入数据保证无重边无自环, 且 1 号点一定可以走到 n 号点
输出
输出一行一个实数, 即最少的期望花费, 当绝对或者相对误差不超过 10^{-6} 时视为正确
样例输入
- 5 8
- 1 2
- 1 3
- 1 4
- 2 3
- 2 4
- 3 5
- 5 4
- 2 5
样例输出
4.1111111111
题解
期望 dp + 堆优化 Dijkstra
设 $f[i]$ 表示 $i$ 到终点的期望步数, 那么有:$f[n]=0\ ,\ f[x]=\frac{\sum\limits_{(x,y)}\text{min}(f[x],f[y])+1}{d[x]}$ , 其中 $d[x]$ 表示 $x$ 的度数
套路: 对于这种 初始只有一个点的 dp 值确定其它点的 dp 值与其相邻的点有关 的图上 dp, 考虑使用类似最短路的方式转移
初始的时候除了 $n$ 以外, 每个点的 $\text{min}(f[x],f[y])$ 都取 $f[x]$ ,dp 值为 $+\infty$
然后从 $n$ 号点开始最短路转移: 对于当前的点 $i$ , 如果某个相邻的 $j$ 有 $f[j]>f[i]$ , 则对于 $f[j]$ 的计算来说,$\text{min}(f[j],f[i])$ 取 $f[i]$ 更优此时更新 $j$ 的 dp 值, 并将 $j$ 加入到待用于更新其它点的集合中
注意到: 如果使用 $f[i]$ 将 $f[j]$ 更新为 $f[j]$ , 那么显然有 $f[i]\le f[j]\le f[j]$ (等号在 $f[i]=f[j]$ 时取到), 满足堆优化 Dijkstra 的贪心策略 (当前最小的一定不会再被更新到更小), 因此可以使用 dp 值小根堆来维护待用于更新其它点的集合, 使用类似堆优化 Dijkstra 的方式转移即可
最终的答案就是 $f[1]$
时间复杂度 $O(m\log n)$
- #include
- #include
- #include
- #define N 300010
- using namespace std;
- typedef pair<double , int> pr;
- priority_queue q;
- double s[N] , f[N];
- int head[N] , to[N << 1] , next[N << 1] , cnt , vis[N] , d[N] , c[N];
- inline void add(int x , int y)
- {
- to[++cnt] = y , next[cnt] = head[x] , head[x] = cnt;
- }
- int main()
- {
- int n , m , i , x , y;
- scanf("%d%d" , &n , &m);
- for(i = 1 ; i <= m ; i ++ ) scanf("%d%d" , &x , &y) , add(x , y) , add(y , x) , d[x] ++ , d[y] ++ ;
- q.push(pr(0 , n));
- while(!q.empty())
- {
- x = q.top().second , q.pop();
- if(vis[x]) continue;
- vis[x] = 1;
- for(i = head[x] ; i ; i = next[i])
- if(!vis[to[i]])
- c[to[i]] ++ , s[to[i]] += f[x] , f[to[i]] = (s[to[i]] + d[to[i]]) / c[to[i]] , q.push(pr(-f[to[i]] , to[i]));
- }
- printf("%lf\n" , f[1]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2515851.html