「NOI2005」聪聪与可可-期望dp

给定一个 $n$ 个点, $m$ 条边的无向图。聪聪开始的时候在 S,可可在节点 T 处。以后的每个时间单位,可可都会选择去相邻的景点(可能有多个)中的一个或停留在原景点不动。而去这些地方所发生的概率是相等的。假设有 $P$ 个景点与景点 M 相邻,它们分别是景点 R、 景点 S,……,景点 Q,在时刻 $i$ 可可处在景点 M,则在 $i+1$ 时刻,可可有 $\frac{1}{1+P}$ 的可能在景点 R,有 $\frac{1}{1+P}$ 的可能在景点 S,……,有 $\frac{1}{1+P}$ 的可能在景点 Q,还有 $\frac{1}{1+P}$ 的可能停在景点 M

当聪聪在景点 C 时,她会选一个更靠近可可的景点,如果这样的景点有多个,她会选一个标号最小的景点。如果走完第一次移动以后仍然没吃到可可,她还可以在本段时间内再向可可进行一次移动。

在每个时间单位,假设聪聪先走,可可后走。在某一时刻,若聪聪和可可位于同一个景点,则可怜的可可就被吃掉了。

请求出平均情况下,聪聪用几个时间单位就可能吃到可可。

链接

Luogu P4206

题解

有趣的期望dp。

我们注意到,如果我们知道可可和聪聪的位置,那么聪聪的两次移动我们都是唯一的。

所以我们用 $n$ 次 $\text{bfs}$ 处理出所有点对间的最短路,然后针对 $n$ 个可可可能在的点,对每个节点进行一次遍历(边),找到最近的出度。以上两个过程都是 $O(n^2)$ 的。

现在我们就可以进行转移了。

设 $dp[u][v]$ 为聪聪在 $u$ ,可可在 $v$ 时的期望步数,然后转移即可。注意到我们需要遍历 $v$ 这个点对应的所有的边,但是无向图的话,所有的边会被遍历两遍,所以对于每个 $v$ ,转移是 $O(n)$ 的,然后转移的复杂度也是 $O(n^2)$ 。

代码

点击切换显示状态
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <cstdio>
#include <vector>
#include <queue>
#include <unistd.h>
using namespace std;

const int MAXN = 1100;

int n,m,s,t;

vector<int> edge[MAXN];
int dis[MAXN][MAXN],near[MAXN][MAXN];
double dp[MAXN][MAXN];
queue<int> q;

void init(){
scanf("%d %d %d %d",&n,&m,&s,&t);
for(int i = 1;i<=m;i++){
int u,v;
scanf("%d %d",&u,&v);
edge[u].push_back(v);
edge[v].push_back(u);
}
}

void bfs(int st){
while(!q.empty()) q.pop();
q.push(st);dis[st][st] = 0;

while(!q.empty()){
int nown = q.front();q.pop();
// printf("%d\n",nown);
for(unsigned i = 0;i<edge[nown].size();i++){
int v = edge[nown][i];
// printf(" v:%d\n",v);
if(dis[st][v] == 0 && v != st){
dis[st][v] = dis[st][nown] + 1;
q.push(v);
}
}
}
}

void get_near(int to){
for(int nown = 1;nown<=n;nown++){
if(nown == to) continue;//cautious
near[nown][to] = 0x3f3f3f3f;
for(unsigned i = 0;i<edge[nown].size();i++){
int v = edge[nown][i];
if(dis[v][to] < dis[nown][to] && near[nown][to] > v){
near[nown][to] = v;
}
}
}
}

double dfs(int u,int v){
int uu = u,vv = v;
if(dp[uu][vv] != 0) return dp[u][v];
if(u == v) return 0;
if(near[u][v] == v || near[near[u][v]][v] == v){
return dp[u][v] = 1;
}
u = near[near[u][v]][v];
double ans = 0;
for(unsigned i = 0;i<edge[v].size();i++){
int to = edge[v][i];
ans += (dfs(u,to)+1);
}
ans += dfs(u,v)+1;
return dp[uu][vv] = ans/(edge[v].size()+1);
}

void solve(){
for(int i = 1;i<=n;i++) bfs(i);
for(int i = 1;i<=n;i++) get_near(i);
double ans = dfs(s,t);
printf("%.3lf\n",ans);
}

int main(){
init();
solve();
return 0;
}