CF446DDZYLovesGames

https://www.luogu.com.cn/problem/CF446D

首先肯定是转换为求出$g[i][j]$表示从第$i$个陷阱到第$j$个陷阱&＃xff0c;不经过其他陷阱&＃xff08;相当于是走一步&＃xff09;的概率&＃xff1b;
1单独处理一下
然后把这个矩阵$k-2$次方即可(走k-1步)

然后现在来考虑怎么求出$g$

把所有关键点的出边全部删掉
记$f[i][j]$表示原图的第$i$个点(不是关键点)&＃xff0c;到第$j$个关键点的概率
这个跑$n$次高斯消元&＃xff08;对于每个结束点跑一次&＃xff09;就可以得出来以每个关键点结束的概率

然后$g[i][j]$就枚举$i$的出边$v$然后通过f来求出

这样是O(n4)O(n^4)O(n4)&＃xff0c;不太行

容易发现&＃xff0c;对于每个结束点的矩阵&＃xff08;方程组&＃xff09;&＃xff0c;只有最后一列&＃xff08;常数&＃xff09;是不同的
所以可以吧常数项全部丢到后面&＃xff0c;一次消元&＃xff0c;一次性全部求出来

具体实现看代码吧
code:

#include
#define N 605
using namespace std;
int tot;
struct MT {double a[105][105];void clear() {for(int i &＃61; 0; i <&＃61; tot; i &＃43;&＃43;)for(int j &＃61; 0; j <&＃61; tot; j &＃43;&＃43;) a[i][j] &＃61; 0;}void I() {for(int i &＃61; 1; i <&＃61; tot; i &＃43;&＃43;) a[i][i] &＃61; 1;}
} ans, b;
MT mul(MT a, MT b) {MT c; c.clear();for(int k &＃61; 1; k <&＃61; tot; k &＃43;&＃43;)for(int i &＃61; 1; i <&＃61; tot; i &＃43;&＃43;)for(int j &＃61; 1; j <&＃61; tot; j &＃43;&＃43;)c.a[i][j] &＃43;&＃61; a.a[i][k] * b.a[k][j];return c;
}
MT qpow(MT x, int y) {MT ret; ret.clear(); ret.I();for(; y; y >>&＃61; 1, x &＃61; mul(x, x)) if(y & 1) ret &＃61; mul(ret, x);return ret;
}
double a[N][N];
int o[N], p[N], d[N], gs[N][N], n, m, k;
void Guass(int n) {for(int i &＃61; 1; i <&＃61; n; i &＃43;&＃43;) {int j &＃61; i;for(int k &＃61; i &＃43; 1; k <&＃61; n; k &＃43;&＃43;) if(abs(a[j][i]) < abs(a[k][i])) j &＃61; k;if(j !&＃61; i) swap(a[j], a[i]);double d &＃61; a[i][i];for(int j &＃61; i; j <&＃61; n &＃43; tot; j &＃43;&＃43;) a[i][j] /&＃61; d;for(int j &＃61; 1; j <&＃61; n; j &＃43;&＃43;) {if(j &＃61;&＃61; i) continue;double t &＃61; a[j][i] / a[i][i];for(int k &＃61; i; k <&＃61; n &＃43; tot; k &＃43;&＃43;)a[j][k] -&＃61; t * a[i][k];}}
}
int main() {scanf("%d%d%d", &n, &m, &k);for(int i &＃61; 1; i <&＃61; n; i &＃43;&＃43;) {scanf("%d", &o[i]);if(o[i]) p[&＃43;&＃43; tot] &＃61; i;}for(int i &＃61; 1; i <&＃61; m; i &＃43;&＃43;) {int u, v;scanf("%d%d", &u, &v);d[u] &＃43;&＃43;, d[v] &＃43;&＃43;; gs[u][v] &＃43;&＃43;, gs[v][u] &＃43;&＃43;;}for(int i &＃61; 1; i <&＃61; n; i &＃43;&＃43;) {if(!o[i]) {a[i][i] &＃61; -1;for(int j &＃61; 1; j <&＃61; n; j &＃43;&＃43;) a[i][j] &＃43;&＃61; 1.0 * gs[i][j] / d[i];} else {a[i][i] &＃61; 1;int pos &＃61; 0;for(int j &＃61; 1; j <&＃61; tot; j &＃43;&＃43;) if(p[j] &＃61;&＃61; i) pos &＃61; j;a[i][n &＃43; pos] &＃61; 1;}}
// for(int i &＃61; 1; i <&＃61; n; i &＃43;&＃43;) {
// for(int j &＃61; 1; j <&＃61; n &＃43; tot; j &＃43;&＃43;) printf("%.2lf ", a[i][j]); printf("\n");
// }Guass(n);for(int i &＃61; 1; i <&＃61; tot; i &＃43;&＃43;) ans.a[1][i] &＃61; a[1][n &＃43; i];for(int i &＃61; 1; i <&＃61; tot; i &＃43;&＃43;)for(int j &＃61; 1; j <&＃61; tot; j &＃43;&＃43;) {for(int k &＃61; 1; k <&＃61; n; k &＃43;&＃43;) b.a[i][j] &＃43;&＃61; gs[p[i]][k] * a[k][j &＃43; n];b.a[i][j] /&＃61; d[p[i]];}ans &＃61; mul(ans, qpow(b, k - 2));printf("%.9lf", ans.a[1][tot]);return 0;
}