发现答案其实与这个点炸弹经过的次数有关，因为只要知道了这个点炸弹经过次数 \(w\)，这个点答案就能算出：\(w\times \frac{p}{q}\)
就想到设 \(f_u\) 为 \(u\) 点炸弹经过次数
\(u\) 点经过次数便可以由有连边的 \(v\) 点推来，要满足 \(v\) 点此时炸弹没爆炸且 \(deg_v\) 条边中选了 \(u\) 这一条边，要注意若为 \(1\) 号点起始经过了 \(1\) 次
\(f_u = \begin{cases}(1 - \frac{p}{q}) \sum \frac{f_v}{deg_v}& (u \not = 1)\\ 1 + (1 - \frac{p}{q}) \sum \frac{f_v}{deg_v} & (u = 1)\end{cases}\)
然后会发现这个东西有环，用高斯消元处理得到对应的 \(f_u\) 算出答案即可
时间复杂度 \(O(n^3)\)
#include<bits/stdc++.h>
using namespace std;
#define ldouble long double
const int N = 3e2 + 5;
vector<int> to[N];
int deg[N];
void add(int u, int v) {
to[u].push_back(v); deg[v]++;
return ;
}
ldouble g[N][N];
ldouble ans[N];
int main() {
int n, m, p, q;
scanf("%d%d%d%d", &n, &m, &p, &q);
for (int i = 1; i <= m; i++) {
int x, y;
scanf("%d%d", &x, &y);
add(x, y); add(y, x);
}
ldouble s = 1.0 * p / q;
g[1][n + 1] = 1.0;
for (int i = 1; i <= n; i++) {
g[i][i] = 1.0;
for (int j : to[i]) {
g[i][j] = -(1.0 - s) / deg[j];
}
}
for (int i = 1; i <= n; i++) {
int h = i;
for (int j = i + 1; j <= n; j++) {
if (fabs(g[j][i]) > fabs(g[h][i])) {
h = j;
}
}
swap(g[i], g[h]);
for (int j = n + 1; j >= i; j--) {
g[i][j] /= g[i][i];
}
for (int j = i + 1; j <= n; j++) {
for (int k = n + 1; k >= i; k--) {
g[j][k] -= g[j][i] * g[i][k];
}
}
}
for (int i = n; i >= 1; i--) {
ans[i] = g[i][n + 1];
for (int j = i - 1; j >= 1; j--) {
g[j][n + 1] -= ans[i] * g[j][i];
}
}
for (int i = 1; i <= n; i++) {
printf("%.9Lf\n", ans[i] * s);
}
return 0;
}