这题主要有两种做法：1种是用逆矩阵，转移时无须高斯消元。2是将常数项回代。这里主要介绍第一种。

首先题里少个条件：点权非负。设f [ i ][ j ]表示hp为i时，到达j点的期望次数。

那么若点权为正，直接转移：f [ i + w[ j ] ][ i ]对f [ i ][ j ]的贡献为f[ i+w[j] ]/d[ i ]（d[i]表示点i的出度）

若点权为0，则需高斯消元，单次消元复杂度（n^3）显然会炸，我们考虑优化。、

对于高斯消元，有一个结论：系数矩阵*答案矩阵=常数矩阵（用方程组的定义来理解，挺简单的，虽然我想了好久）

将系数矩阵换到右边，就变成了 答案矩阵=常数矩阵×系数矩阵的逆

对于本题而言，系数矩阵是不变的，变化的只有常数矩阵，而常数矩阵O（m）即可处理出，因此我们可以预处理出系数矩阵的逆矩阵

 

 1 #include<bits/stdc++.h>
 2 #define eps 1e-8
 3 using namespace std;
 4 int n,m,hp,a[155],tot,to[10005],fi[155],ne[10005],du[155];
 5 double c[155][155],b[155][155],d[155][155],f[10005][152],dp[152],ans;
 6 inline void add(int x,int y)
 7 {
 8     ne[++tot]=fi[x];
 9     fi[x]=tot;
10     to[tot]=y;
11 }
12 int main()
13 {
14     scanf("%d%d%d",&n,&m,&hp);
15     for(int i=1;i<=n;i++)
16         scanf("%d",&a[i]);
17     for(int i=1,x,y;i<=m;i++)
18     {
19         scanf("%d%d",&x,&y);
20         add(x,y),du[x]++;
21         if(x!=y)
22             add(y,x),du[y]++;
23     }
24     for(int i=1;i<n;i++)
25         for(int j=fi[i];j;j=ne[j])
26         {
27             int y=to[j];
28             if(!a[y])
29             {
30                 c[y][i]+=1.0/du[i];
31             }
32         }
33     for(int i=1;i<=n;i++)
34         b[i][i]=1,c[i][i]--;
35       for(int i=1;i<=n;i++)
36       {
37           int k=i;
38           for(int j=i+1;j<=n;j++)
39               if(fabs(c[j][i])>fabs(c[k][i]))
40                   k=j;
41           for(int j=1;j<=n;j++)swap(c[i][j],c[k][j]),swap(b[i][j],b[k][j]);
42           if(fabs(c[i][i])<eps)continue;
43           double r=c[i][i];
44           for(int j=1;j<=n;j++)
45               c[i][j]/=r,b[i][j]/=r;
46           for(int j=1;j<=n;j++)
47           {
48               if(i==j)continue;
49               double r=c[j][i];
50               for(int k=1;k<=n;k++)
51                   c[j][k]-=r*c[i][k],b[j][k]-=r*b[i][k];
52           }
53       }
54       f[hp][1]=-1;
55     for(int i=hp;i;i--)
56     {
57         for(int j=1;j<=n;j++)
58             for(int k=1;k<=n;k++)
59                 dp[j]+=f[i][k]*b[j][k];
60         ans+=dp[n];
61         for(int j=1;j<n;j++)
62         {
63             for(int k=fi[j];k;k=ne[k])
64             {
65                 int y=to[k];
66                 if(a[y]&&i>a[y])
67                     f[i-a[y]][y]-=1.0*dp[j]/du[j];
68             }
69             dp[j]=0;
70         }
71         dp[n]=0;
72     }
73     printf("%.8lf",ans);
74     return 0;
75 }

View Code