#题意简述
一个无向图，节点1有一个炸弹，在每个单位时间内，有p/q的概率在这个节点炸掉，有1-p/q的概率随机选择一条出去的路到其他的节点上。问最终炸弹在每个节点上爆炸的概率。
#简要做法
求期望，即求每个节点炸弹经过次数的期望。设f[i]为经过i节点的次数，则有$f[u] = \sum_{(u,v)\in E}\frac{1}{deg_v}(1-\frac{p}{q})f[v]$，（意思是一个节点不爆炸就有等概率传给临边）其中f[1]还要再加1，因为初始还有一次。有了这些方程后高斯消元即可。
#参考代码
|
|
|
using namespace std; |
const int maxn = 305; |
int n, m, p, q; |
vector<int> G[maxn]; |
double a[maxn][maxn]; |
void Gauss() { |
for(int i = 1; i <= n; ++i) { |
int mx = i; |
for(int j = i + 1; j <= n; ++j) |
if(fabs(a[j][i]) > fabs(a[mx][i])) mx = j; |
for(int j = i; j <= n + 1; ++j) swap(a[i][j], a[mx][j]); |
for(int j = 1; j <= n; ++j) { |
if(i == j) continue; |
double tmp = a[j][i] / a[i][i]; |
for(int k = i; k <= n + 1; ++k) a[j][k] -= a[i][k] * tmp; |
} |
} |
} |
int main() { |
ios::sync_with_stdio(false); |
cin.tie(nullptr), cout.tie(nullptr); |
|
freopen("testdata.in", "r", stdin); |
|
cin >> n >> m >> p >> q; |
int u, v; |
for(int i = 1; i <= m; ++i) { |
cin >> u >> v; |
G[u].push_back(v); |
G[v].push_back(u); |
} |
double P = (double)p / q; |
for(int i = 1; i <= n; ++i) { |
a[i][i] = 1; |
for(int j = 0; j < G[i].size(); ++j) { |
int to = G[i][j]; |
a[i][to] -= (1 - P) / G[to].size(); |
} |
} |
a[1][n + 1] = 1; |
Gauss(); |
for(int i = 1; i <= n; ++i) |
cout << setprecision(9) << fixed << P * a[i][n + 1] / a[i][i] << endl; |
return 0; |
} |