高斯消元与期望值计算

在概率论中，炸弹到目标 i 不爆炸的期望值 f[i] 的计算，通常可以借助线性代数的方法来解决。通过高斯消元技术，我们可以高效地求解相关矩阵的逆矩阵，从而得到所需的期望值。

需要注意的是，题目中的概率表达式 p/q 实际上是 1 - p/q。这一点在计算过程中需要特别留意，以避免计算错误。

此外，有关程序输出为 -0.00000 的问题，不加 EPS（极小值）会导致浮点数精度问题。这种情况通常发生在数值计算中，当结果远小于或接近零时，为了避免误差积累，通常会设置一个极小的 EPS 值。

以下是该问题的具体实现代码：

#include 
   
    #define IL inline#define RG register#define Fill(a, b) memset(a, b, sizeof(a))using namespace std;typedef long long ll;const int _(505);const int __(100005);IL ll Input() {    RG char c = getchar();    RG ll x = 0, z = 1;    for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;    for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);    return x * z;}int n, m, fst[_], nxt[__], cnt, to[__], dg[_];double ans, f[_], a[_][_], p, q;IL void Add(RG int u, RG int v) {    to[cnt] = v;    nxt[cnt] = fst[u];    fst[u] = cnt++;    ++dg[v];}IL void Gauss() {    for(RG int i = 1; i < n; ++i)        for(RG int j = i + 1; j <= n; ++j) {            RG double div = a[j][i] / a[i][i];            for(RG int k = 1; k <= n + 1; ++k)                a[j][k] -= a[i][k] * div;        }    for(RG int i = n; i; --i) {        f[i] = a[i][n + 1] / a[i][i];        for(RG int j = i - 1; j; --j)            a[j][n + 1] -= f[i] * a[j][i];    }}int main(RG int argc, RG char* argv[]) {    n = Input();    m = Input();    Fill(fst, -1);    q = Input();    q /= Input();    p = 1.0 - q;    for(RG int i = 1, u, v; i <= m; ++i) {        u = Input();        v = Input();        Add(u, v);        Add(v, u);    }    for(RG int u = 1; u <= n; ++u) {        a[u][u] = -1.0;        for(RG int e = fst[u]; e != -1; e = nxt[e])            a[to[e]][u] = p / dg[u];    }    a[1][n + 1] = -1.0;    Gauss();    for(RG int i = 1; i <= n; ++i) {        f[i] *= q;        if(fabs(f[i]) < 1e-9) f[i] = 0;    }    for(RG int i = 1; i <= n; ++i) printf("%.9lf\n", f[i]);    return 0;}

代码中定义了多个关键变量和函数，主要用于矩阵运算和高斯消元过程。通过高斯消元方法，我们可以对矩阵进行化简，最终求解出各个节点的期望值 f[i]。

代码的核心逻辑包括以下几个步骤：

输入处理：从标准输入读取数据，包括矩阵的大小 n，边数 m，以及相关的参数 p 和 q。

图的构建：通过 Add 函数构建图的邻接表结构。

矩阵初始化：将矩阵 a 初始化为对角线元素为 -1.0，其他元素根据图的结构和概率参数 p 和 q 计算。

高斯消元：执行高斯消元算法，求解矩阵的逆矩阵。

期望值计算：通过逆矩阵的元素计算各节点的期望值 f[i]，并调整结果以避免精度误差。

输出结果：输出每个节点的期望值，保留九位小数。

整个程序的设计思路是通过高斯消元方法求解线性方程组，从而计算炸弹到各目标点的期望不爆炸情况。这一方法在概率问题中的应用非常广泛，能够有效解决复杂的期望值计算问题。

转载地址：http://evufk.baihongyu.com/

你可能感兴趣的文章