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$方程组中只有常数项不同
那么我们可以先不考虑常数项, 求出每一个解是如何由常数项线性构造出来的
每次将常数项带入就好了

#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);
}