NekoMio's Blog

美しいものが起こることを常に信じている

Description

让我们继续JC和DZY的故事。
“你是我的小丫小苹果,怎么爱你都不嫌多!”
“点亮我生命的火,火火火火火!”
话说$JC$历经艰辛来到了城市$B$,但是由于他的疏忽$DZY$偷走了他的小苹果!没有小苹果怎么听歌!他发现邪恶的$DZY$把他的小苹果藏在了一个迷宫里。$JC$在经历了之前的战斗后他还剩下$hp$点血。开始$JC$在$1$号点,他的小苹果在$N$号点。$DZY$在一些点里放了怪兽。当$JC$每次遇到位置在$i$的怪兽时他会损失$A_i$点血。当$JC$的血小于等于$0$时他就会被自动弹出迷宫并且再也无法进入。
但是$JC$迷路了,他每次只能从当前所在点出发等概率的选择一条道路走。所有道路都是双向的,一共有$m$条,怪兽无法被杀死。现在$JC$想知道他找到他的小苹果的概率。
P.S.大家都知道这个系列是提高组模拟赛,所以这是一道送分题balabala

Input

第一行三个整数表示$n$,$m$,$hp$。接下来一行整数,第$i$个表示$JC$到第$i$个点要损失的血量。保证第$1$个和$n$个数为$0$。接下来$m$行每行两个整数$a$,$b$表示$ab$间有一条无向边。

Output

仅一行,表示JC找到他的小苹果的期望概率,保留八位小数。

Sample Input

1
2
3
4
5
3 3 2
0 1 0
1 2
1 3
2 3

Sample Output

1
0.87500000

HINT

对于$100%$的数据 $2 \leq n \leq 150$,$hp \leq 10000$,$m \leq 5000$,保证图联通。

题解

设$F[i][j]$ 表示剩余血量为$i$现在在点$j$的概率
首先相等的血量之间的转移有环, 要用高斯消元
然而这样的复杂度为$hp*n^3$是不能过的
然后可以观察到,对于不同的$hp$方程组中只有常数项不同
那么我们可以先不考虑常数项, 求出每一个解是如何由常数项线性构造出来的
每次将常数项带入就好了

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
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int MAXN = 155;
struct edge
{
int END, next;
}v[10005];
int first[MAXN], p;
int du[MAXN], t[MAXN];
void add(int a, int b)
{
v[p].END = b;
v[p].next = first[a];
first[a] = p++;
}
double a[MAXN][MAXN], c[MAXN][MAXN];
double DP[10005][MAXN], tmp[MAXN];
void Gauss_Jordan(int n)
{
for (int i = 1; i <= n; i++)
{
int k = i;
for (int j = i + 1; j <= n; j++)
if (fabs(a[j][i]) > fabs(a[k][i]))
k = j;
if (k != i)
{
for (int j = i; j <= n; j++)
swap(a[i][j], a[k][j]);
for (int j = 1; j <= n; j++)
swap(c[i][j], c[k][j]);
}
for (int j = 1; j <= n; j++)
if (j != i)
{
double t = a[j][i] / a[i][i];
for (k = i; k <= n; k++)
a[j][k] -= a[i][k] * t;
for (k = 1; k <= n; k++)
c[j][k] -= c[i][k] * t;
}
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
c[i][j] /= a[i][i];
}

int main()
{
int n = read(), m = read(), hp = read();
memset (first, -1, sizeof (first));
for (int i = 1; i <= n; i++) t[i] = read();
for (int i = 1; i <= m; i++)
{
int b = read(), d = read();
add(b, d), du[b]++;
if (b != d) add(d, b), du[d]++;
}
for (int i = 1; i <= n; i++)
{
a[i][i] = 1, c[i][i] = 1;
if (t[i] == 0)
{
for (int j = first[i]; j != -1; j = v[j].next)
if (v[j].END != n)
a[i][v[j].END] -= 1.0 / du[v[j].END];
}
}
Gauss_Jordan(n);
double ans = 0;
for (int i = hp; i >= 1; i--)
{
memset (tmp, 0, sizeof (tmp));
if (i == hp)
tmp[1] = 1;
for (int j = 1; j <= n; j++)
if (t[j] && i + t[j] <= hp)
for (int k = first[j]; k != -1; k = v[k].next)
if (v[k].END != n)
tmp[j] += DP[i + t[j]][v[k].END] / du[v[k].END];
for (int j = 1; j <= n; j++)
for (int k = 1; k <= n; k++)
DP[i][j] += tmp[k] * c[j][k];
ans += DP[i][n];
}
printf ("%.8f\n", ans);
// while (1);
}

本文作者 : NekoMio
知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
本文链接 : https://www.nekomio.com/2018/03/24/140/

本文最后更新于 天前,文中所描述的信息可能已发生改变