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
3 3 2
0 1 0
1 2
1 3
2 3
Sample Output
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);
}