题解
我们考虑列出期望方程组，\(dp[i][j]\)表示在第\(i\)个点血量为\(j\)的时候到达\(N\)点的概率，所有的\(dp[N][j]\)都是1，所有\(j < 0\)都是0
答案是\(dp[1][hp]\)
\(dp[u][j] = \sum_{v} \frac{1}{deg[u]}dp[v][j - a[v]]\)
我们发现这个方程在j不同的时候，只有常数项发生改变，剩下的系数不变
于是我们把常数项变成一个列向量，把需要消元的系数矩阵求一个逆，每次计算常数项，用常数项乘逆矩阵得到每一个血量的\(dp\)值即可
注意判自环= =
代码
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define pdi pair<db,int>
#define mp make_pair
#define pb push_back
#define enter putchar(‘\n‘)
#define space putchar(‘ ‘)
#define eps 1e-8
#define mo 974711
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
res = 0;char c = getchar();T f = 1;
while(c < ‘0‘ || c > ‘9‘) {
if(c == ‘-‘) f = -1;
c = getchar();
}
while(c >= ‘0‘ && c <= ‘9‘) {
res = res * 10 + c - ‘0‘;
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar(‘-‘);}
if(x >= 10) {
out(x / 10);
}
putchar(‘0‘ + x % 10);
}
int N,M,hp,deg[155],blood[155];
struct node {
int to,next;
}E[100005];
int sumE,head[155];
db b[155],dp[155][10005],c[155];
void add(int u,int v) {
E[++sumE].next = head[u];
E[sumE].to = v;
head[u] = sumE;
}
struct Matrix {
db f[155][155];
Matrix() {memset(f,0,sizeof(f));}
void unit() {
for(int i = 1 ; i <= N ; ++i) {
f[i][i] = 1.0;
}
}
friend Matrix operator * (const Matrix &a,const Matrix &b) {
Matrix c;
for(int i = 1 ; i <= N ; ++i) {
for(int j = 1 ; j <= N ; ++j) {
for(int k = 1 ; k <= N ; ++k) {
c.f[i][j] += a.f[i][k] * b.f[k][j];
}
}
}
return c;
}
friend Matrix operator ~(Matrix a) {
Matrix b;
b.unit();
for(int i = 1 ; i <= N ; ++i) {
int l = i;
for(int j = i + 1; j <= N ; ++j) {
if(fabs(a.f[j][i]) > fabs(a.f[l][i])) l = j;
}
if(i != l) {
for(int j = 1 ; j <= N ; ++j) {
swap(a.f[i][j],a.f[l][j]);
swap(b.f[i][j],b.f[l][j]);
}
}
db t = 1.0 / a.f[i][i];
for(int j = 1 ; j <= N ; ++j) {
a.f[i][j] *= t;
b.f[i][j] *= t;
}
for(int j = 1 ; j <= N ; ++j) {
if(i == j) continue;
db t = a.f[j][i];
for(int k = 1 ; k <= N ; ++k) {
a.f[j][k] -= t * a.f[i][k];
b.f[j][k] -= t * b.f[i][k];
}
}
}
return b;
}
}A;
void Solve() {
read(N);read(M);read(hp);
int u,v;
for(int i = 1 ; i <= N ; ++i) read(blood[i]);
for(int i = 1 ; i <= M ; ++i) {
read(u);read(v);
if(u == v) {add(u,v);++deg[u];}
else {add(u,v);add(v,u);++deg[u];++deg[v];}
}
for(int u = 1 ; u <= N ; ++u) {
if(u == N) {
b[u] = 1;A.f[u][u] = 1;continue;
}
A.f[u][u] = 1;
for(int i = head[u] ; i ; i = E[i].next) {
int v = E[i].to;
if(v == N) {b[u] += 1.0 / deg[u];}
else if(blood[v] == 0){
A.f[v][u] -= 1.0 / deg[u];
}
}
}
A = ~A;
for(int i = 1 ; i <= hp ; ++i) {
for(int u = 1 ; u <= N ; ++u) {
c[u] = b[u];
if(u == N) continue;
for(int h = head[u] ; h ; h = E[h].next) {
int v = E[h].to;
if(blood[v] && i > blood[v]) {
c[u] += (1.0 / deg[u]) * dp[v][i - blood[v]];
}
}
}
for(int u = 1 ; u <= N ; ++u) {
for(int k = 1 ; k <= N ; ++k) {
dp[u][i] += c[k] * A.f[k][u];
}
}
}
printf("%.8lf\n",dp[1][hp]);
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
return 0;
}