941 字
5 分钟
BZOJ3640 JC的小苹果

Description#

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

Input#

第一行三个整数表示nnmmhphp。接下来一行整数,第ii个表示JCJC到第ii个点要损失的血量。保证第11个和nn个数为00。接下来mm行每行两个整数aabb表示abab间有一条无向边。

Output#

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

Sample Input#

3 3 2
0 1 0
1 2
1 3
2 3

Sample Output#

0.87500000

HINT#

对于100%100\%的数据 2n1502 \leq n \leq 150hp10000hp \leq 10000m5000m \leq 5000,保证图联通。

题解#

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

#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);
}
BZOJ3640 JC的小苹果
https://www.nekomio.com/posts/140/
作者
NekoMio
发布于
2018-03-24
许可协议
CC BY-NC-SA 4.0