BZOJ3640 JC的小苹果 - 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#

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
#include <cstdio>
2
#include <cstring>
3
#include <algorithm>
4
#include <cmath>
5
using namespace std;
6
inline int read()
7
{
8
    int x=0,f=1;char ch=getchar();
9
    while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
10
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
11
    return x*f;
12
}
13
const int MAXN = 155;
14
struct edge
15
{
16
    int END, next;
17
}v[10005];
18
int first[MAXN], p;
19
int du[MAXN], t[MAXN];
20
void add(int a, int b)
21
{
22
    v[p].END = b;
23
    v[p].next = first[a];
24
    first[a] = p++;
25
}
26
double a[MAXN][MAXN], c[MAXN][MAXN];
27
double DP[10005][MAXN], tmp[MAXN];
28
void Gauss_Jordan(int n)
29
{
30
    for (int i = 1; i <= n; i++)
31
    {
32
        int k = i;
33
        for (int j = i + 1; j <= n; j++)
34
            if (fabs(a[j][i]) > fabs(a[k][i]))
35
                k = j;
36
        if (k != i)
37
        {
38
            for (int j = i; j <= n; j++)
39
                swap(a[i][j], a[k][j]);
40
            for (int j = 1; j <= n; j++)
41
                swap(c[i][j], c[k][j]);
42
        }
43
        for (int j = 1; j <= n; j++)
44
            if (j != i)
45
            {
46
                double t = a[j][i] / a[i][i];
47
                for (k = i; k <= n; k++)
48
                    a[j][k] -= a[i][k] * t;
49
                for (k = 1; k <= n; k++)
50
                    c[j][k] -= c[i][k] * t;
51
            }
52
    }
53
    for (int i = 1; i <= n; i++)
54
        for (int j = 1; j <= n; j++)
55
            c[i][j] /= a[i][i];
56
}
57

58
int main()
59
{
60
    int n = read(), m = read(), hp = read();
61
    memset (first, -1, sizeof (first));
62
    for (int i = 1; i <= n; i++) t[i] = read();
63
    for (int i = 1; i <= m; i++)
64
    {
65
        int b = read(), d = read();
66
        add(b, d), du[b]++;
67
        if (b != d) add(d, b), du[d]++;
68
    }
69
    for (int i = 1; i <= n; i++)
70
    {
71
        a[i][i] = 1, c[i][i] = 1;
72
        if (t[i] == 0)
73
        {
74
            for (int j = first[i]; j != -1; j = v[j].next)
75
                if (v[j].END != n)
76
                    a[i][v[j].END] -= 1.0 / du[v[j].END];
77
        }
78
    }
79
    Gauss_Jordan(n);
80
    double ans = 0;
81
    for (int i = hp; i >= 1; i--)
82
    {
83
        memset (tmp, 0, sizeof (tmp));
84
        if (i == hp)
85
            tmp[1] = 1;
86
        for (int j = 1; j <= n; j++)
87
            if (t[j] && i + t[j] <= hp)
88
                for (int k = first[j]; k != -1; k = v[k].next)
89
                    if (v[k].END != n)
90
                        tmp[j] += DP[i + t[j]][v[k].END] / du[v[k].END];
91
        for (int j = 1; j <= n; j++)
92
            for (int k = 1; k <= n; k++)
93
                DP[i][j] += tmp[k] * c[j][k];
94
        ans += DP[i][n];
95
    }
96
    printf ("%.8f\n", ans);
97
    // while (1);
98
}