NKOJ 3893 聪聪和可可（数学期望+递推+最短路）

发表于 |
字数统计: 771字 | 阅读时长 ≈ 4min

P3893【概率】聪聪和可可

问题描述

NKOJ3893

输入格式

数据的第1行为两个整数N和E，以空格分隔，分别表示森林中的景点数和连接相邻景点的路的条数。
第2行包含两个整数C和M，以空格分隔，分别表示初始时聪聪和可可所在的景点的编号。
接下来E行，每行两个整数，第i+2行的两个整数Ai和Bi表示景点Ai和景点Bi之间有一条路。
所有的路都是无向的，即：如果能从A走到B，就可以从B走到A。
输入保证任何两个景点之间不会有多于一条路直接相连，且聪聪和可可之间必有路直接或间接的相连。

输出格式

输出1个实数，四舍五入保留三位小数，表示平均多少个时间单位后聪聪会把可可吃掉。

样例输入 1

4 3
1 4
1 2
2 3
3 4

样例输出 1

1.500

样例输入 2

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

样例输出 2

2.167

令$F[x][y]$表示聪聪在$x$节点，可可在$y$节点时，聪聪吃到可可的期望步数。
那么令$tx=聪聪移动后的位置$
那么如果$x=y$，$F[x][y]=0$
如果$tx=y$，$F[x][y]=1$
否则，令$k=可可可能的移动位置$，$D[y]表示y的度数$
有$F[x][y]=(\sum F[tx][k] \times \frac{1}{D[y]+1})+1 $

然后用最短路算法或者BFS预处理出$tx$即可。

代码：

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
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#define N 1005
#define MM 2005
using namespace std;
int n,m,C,M,D[N],P[N][N];
int TOT,LA[N],NE[MM],EN[MM];
double F[N][N];
queue<int>Q;
int dis[N];
bool mark[N];
void ADD(int x,int y)
{
	TOT++;
	EN[TOT]=y;
	NE[TOT]=LA[x];
	LA[x]=TOT;
}
void SPFA(int s)
{
	int i,x,y;
	memset(dis,60,sizeof(dis));
	Q.push(s);mark[s]=1;dis[s]=0;
	while(Q.size())
	{
		x=Q.front();
		Q.pop();
		mark[x]=0;
		for(i=LA[x];i;i=NE[i])
		{
			y=EN[i];
			if(dis[y]>dis[x]+1||(dis[y]==dis[x]+1&&P[s][y]>P[s][x]))
			{
				dis[y]=dis[x]+1;
				if(P[s][x])P[s][y]=P[s][x];
				else P[s][y]=y;
				if(!mark[y])mark[y]=1,Q.push(y);
			}
		}
	}
}
double DFS(int x,int y)
{
	if(F[x][y])return F[x][y];
	if(x==y)return F[x][y]=0;
	int tx=x,ty=y;
	tx=P[tx][ty];
	if(tx==ty)return F[x][y]=1.0;
	tx=P[tx][ty];
	if(tx==ty)return F[x][y]=1.0;
	double sum=0;
	for(int i=LA[y];i;i=NE[i])
	{
		ty=EN[i];
		sum+=DFS(tx,ty);
	}
	sum+=DFS(tx,y);
	return F[x][y]=sum/(D[y]+1)+1;
}
int main()
{
	int i,x,y;
	scanf("%d%d%d%d",&n,&m,&C,&M);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		ADD(x,y);ADD(y,x);
		D[x]++;D[y]++;
	}
	for(i=1;i<=n;i++)SPFA(i);
	printf("%.3lf",DFS(C,M));
}