BZOJ 5197（CERC 2017）Gambling Guide（数学期望+动态规划+最短路）

发表于 |
字数统计: 739字 | 阅读时长 ≈ 3min

【CERC2017】旅游指南

问题描述

给定一张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方程$dp[x]=\frac{\sum dp[y]}{d[x]}+1$，然后可以用高斯消元处理。

再考虑最优策略，只需要修改一下dp方程，$dp[x]=\frac{\sum min(dp[x],dp[y])}{d[x]}+1$，这里的$min$表示如果$y$不优，那么可以停在原地。因此我们可以假设有$c$个$dp[y]<dp[x]$，那么解方程可以得到$dp[x]=\frac{\sum dp[y]+d[x]}{c}$

然后可以用Dijkstra来进行转移，初始时$dp[n]=0$，然后每次取$dp$值最小的且没用过的$dp[x]$出来，转移到$dp[y]$，具体实现可以看代码。

因为Dijkstra每次选的都是最优的点，那么就可以保证当$x$出堆时，所有$dp[y]<dp[x]$的y都已经讨论过，即当前的$dp[x]$取得最优值。

代码：

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
39
40
41
42
43
44
45
46
47
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#define N 600005
using namespace std;
struct node{double x;int p;};
bool operator<(node a,node b){return a.x>b.x;}
int n,m,c[N],d[N];
int TOT,LA[N],NE[N],EN[N];
double dp[N],sum[N];
bool mark[N];
priority_queue<node>Q;
void ADD(int x,int y)
{
	TOT++;
	EN[TOT]=y;
	NE[TOT]=LA[x];
	LA[x]=TOT;
}
int main()
{
	int i,j,k,x,y,z;
	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((node){0,n});
	while(Q.size())
	{
		node tmp=Q.top();
		Q.pop();x=tmp.p;
		if(mark[x])continue;
		mark[x]=1;
		for(i=LA[x];i;i=NE[i])
		{
			y=EN[i];if(mark[y])continue;
			sum[y]+=dp[x];c[y]++;
			dp[y]=(sum[y]+d[y])/(1.0*c[y]);
			Q.push((node){dp[y],y});
		}
	}
	printf("%.7lf",dp[1]);
}