首先我们列出转移矩阵$M$，$M_{i, j} = \frac {1 - \frac{p} {q}} {deg[i]}$(i,j之间有边)or $M_{i, j} = 0$(i,j之间没边)
则这个矩阵$M_{i, j}$表示的是站在某个点$i$，下一次走到$j$且没有爆炸的概率
我们再看$M^n_{i, j}$，表示的站在某个点$i$，走$n$步以后到达$j$且没有爆炸的概率
故$M^n$的第一列代表了$1$号点到其他所有点的概率，设为列向量$A_n$，则$A_n = M^n * B$，其中$B = (1, 0, 0, 0, ...)^T$
设第n步到各点且爆炸了的概率的列向量为$P_n$，则$P_n = \frac{p} {q} * A_n$
故答案列向量$Ans = \sum_{i = 0} ^ {+\infty} P_i$
把它展开：$Ans = \frac{p} {q} * (\sum_{i = 0} ^ {+\infty} M^i) * B$
由等比数列求和公式，$\sum_{i = 0} ^ {+\infty} M^i = \frac{I} {I - M} = (I - M)^{-1}$
故$Ans = \frac{p} {q} * (I - M)^{-1} * B$，即$(I- M) * Ans = \frac{p} {q} * B$
得到一个线性方程组，我们只要高斯消元即可
/**************************************************************
Problem: 1778
User: rausen
Language: C++
Result: Accepted
Time:200 ms
Memory:2264 kb
****************************************************************/ #include <cstdio>
#include <cmath>
#include <algorithm> using namespace std;
typedef double lf;
const int N = ;
const int M = N * N; inline int read(); struct edge {
int next, to;
edge() {}
edge(int _n, int _t) : next(_n), to(_t) {}
} e[M]; int n, m, deg[N];
int first[N], tot;
lf P, a[N][N], ans[N]; inline void Add_Edges(int x, int y) {
e[++tot] = edge(first[x], y), first[x] = tot;
e[++tot] = edge(first[y], x), first[y] = tot;
++deg[x], ++deg[y];
} #define y e[x].to
inline void build_matrix() {
int p, x;
for (p = ; p <= n; ++p) {
for (x = first[p]; x; x = e[x].next)
a[p][y] = -(1.0 - P) / deg[y];
a[p][p] = ;
}
a[][n + ] = P;
}
#undef y void gauss(int n) {
int i, j, k;
lf tmp;
for (i = ; i <= n; ++i) {
for (k = i, j = i + ; j <= n; ++j)
if (fabs(a[j][i]) > fabs(a[k][i])) k = j;
for (j = i; j <= n + ; ++j) swap(a[i][j], a[k][j]);
for (k = i + ; k <= n; ++k)
for (tmp = -a[k][i] / a[i][i], j = i; j <= n + ; ++j)
a[k][j] += a[i][j] * tmp;
}
for (i = n; i; --i) {
for (j = i + ; j <= n; ++j)
a[i][n + ] -= a[i][j] * ans[j];
ans[i] = a[i][n + ] / a[i][i];
}
} int main() {
int i, j;
n = read(), m = read(), P = 1.0 * read() / read();
for (i = ; i <= m; ++i)
Add_Edges(read(), read());
build_matrix();
gauss(n);
for (i = ; i <= n; ++i)
printf("%.9lf\n", ans[i]);
return ;
} inline int read() {
static int x;
static char ch;
x = , ch = getchar();
while (ch < '' || '' < ch)
ch = getchar();
while ('' <= ch && ch <= '') {
x = x * + ch - '';
ch = getchar();
}
return x;
}