NekoMio's Blog

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

  1. 1. Description
  2. 2. Input
  3. 3. Output
  4. 4. Sample Input
  5. 5. Sample Output
  6. 6. HINT
  • 题解
  • 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/

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