Core Logic and Mathematical Principles
Gaussian elimination is a fundamental algorithm in linear algebra for solving systems of linear equations. In competitive programming, when complex cyclic dependencies exist in probability/expected dynamic programming (DP) (for example, random walks on graphs), making it impossible to fill tables through topological sorting or memoization, Gaussian elimination becomes an effective tool for problem-solving.
1. Construction of Expectation Matrix Equations
Assume there are $n$ states in the graph; we need to maintain the expected cost $f[i]$ from each state to the endpoint. According to the stepwise transition rule of expectation (see Chapter 21.3), each state can be expressed as a linear combination of other states:
$$f[i] = \sum_{j=1}^n p_{i \to j} \cdot f[j] + w_i$$
where $p_{i \to j}$ is the probability of transitioning from state $i$ to state $j$, and $w_i$ is the expected cost incurred in one step.
We can rearrange the unknowns $f[j]$ to the left side of the equation and keep the constant terms on the right side, transforming it into the standard form of a linear equation system:
$$(1 - p_{i \to i})f[i] - \sum_{j \neq i} p_{i \to j} f[j] = w_i$$
This forms an augmented matrix (Augmented Matrix) containing $n$ unknowns and @@@MATH_BLOCK10@@@ equations: $$A = \begin{pmatrix} a{1,1} & a{1,2} & \dots & a{1,n} & | & b1 \ a{2,1} & a{2,2} & \dots & a{2,n} & | & b2 \ \vdots & \vdots & \ddots & \vdots & | & \vdots \ a{n,1} & a{n,2} & \dots & a{n,n} & | & b_n \end{pmatrix}$$
2. Core Steps of the Elimination Algorithm
The essence of Gaussian elimination is to transform the augmented matrix into an upper triangular matrix using elementary row operations, and then to solve all unknowns through back substitution.
- Pivot Selection: When processing the $r$-th column, to minimize numerical arithmetic errors caused by floating-point division and to intercept cases where coefficients are $0$, we need to find the row with the maximum absolute value in the $r$-th column from row $r$ to row $n$, and swap it into the $r$-th row.
- Elimination Process: Use the equation of the current $r$-th row to force all coefficients in the $r$-th column of the rows below (from row $r+1$ to row $n$) to be reduced to $0$.
- Back Substitution: After achieving upper triangular form, the last row's equation has transformed into a single-variable equation $a_{n,n} \cdot f[n] = b_n$, allowing us to directly compute $f[n]$. Then, we can substitute back into preceding equations from bottom to top, resolving the entire expected network in $O(n^3)$ time.
Algorithm Derivation and State Design
Matrix Mapping of the Probabilistic Random Walk Model
Assuming we require the expected total number of steps to walk from the starting point $1$ to the endpoint $n$ on a graph containing self-loops and bidirectional edges.
- State Design: Let $f[i]$ denote the expected number of steps to reach the endpoint $n$ starting from node $i$.
- Boundary State Equation: The endpoint $n$ is definite; its expected steps to itself is $0$. Therefore, the equation for row $n$ is very special and does not require looking at any edges, directly written as:
$$1 \cdot f[n] = 0$$
- Regular State Equations: For any non-terminal node $i$, let its out-degree be $deg[i]$. It will walk equally likely to any adjacent point $v \in to(i)$. The one-step cost is $1$. The equation is:
$$f[i] = \sum_{v \in to(i)} \frac{1}{deg[i]} \cdot f[v] + 1 \implies f[i] - \sum_{v \in to(i)} \frac{1}{deg[i]} f[v] = 1$$
These coefficients are sequentially filled into the matrix as A[i][v], with A[i][i] initialized to $1$ and the constant term A[i][n+1] initialized to $1$.
C++ Standard Source Code
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>
const int MAXN = 200;
const double EPS = 1e-9;
double A[MAXN + 5][MAXN + 6]; // Augmented matrix of size N * (N + 1)
double ans[MAXN + 5]; // Store the final expected values for each state
// Core Gaussian elimination algorithm, returns false if there is no solution or infinitely many solutions
bool gaussian_elimination(int n) {
for (int r = 1; r <= n; ++r) {
// 1. Find the pivot
int pivot = r;
for (int i = r + 1; i <= n; ++i) {
if (std::abs(A[i][r]) > std::abs(A[pivot][r])) {
pivot = i;
}
}
// Swap the pivot row to the current row
if (pivot != r) {
for (int j = 1; j <= n + 1; ++j) {
std::swap(A[r][j], A[pivot][j]);
}
}
// If the pivot is 0, it indicates that this column cannot be eliminated (matrix is singular)
if (std::abs(A[r][r]) < EPS) {
return false;
}
// 2. Normalize the current row's pivot coefficient to 1
double divisor = A[r][r];
for (int j = r; j <= n + 1; ++j) {
A[r][j] /= divisor;
}
// 3. Eliminate downwards
for (int i = r + 1; i <= n; ++i) {
if (std::abs(A[i][r]) > EPS) {
double factor = A[i][r];
for (int j = r; j <= n + 1; ++j) {
A[i][j] -= factor * A[r][j];
}
}
}
}
// 4. Back substitution
for (int i = n; i >= 1; --i) {
ans[i] = A[i][n + 1];
for (int j = i + 1; j <= n; ++j) {
ans[i] -= A[i][j] * ans[j];
}
}
return true;
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n, m;
if (std::cin >> n >> m) {
std::vector<int> deg(n + 1, 0);
std::vector<std::pair<int, int>> edges;
for (int i = 0; i < m; ++i) {
int u, v;
std::cin >> u >> v;
edges.push_back({u, v});
deg[u]++; // Count out-degrees
}
// Initialize the augmented matrix
// Construct expectation transition equations for nodes 1 to n-1
for (int i = 1; i < n; ++i) {
A[i][i] = 1.0;
A[i][n + 1] = 1.0; // One-step cost 1
}
// Fill in transition probability coefficients
for (const auto &edge : edges) {
int u = edge.first;
int v = edge.second;
if (u < n) { // No transition needed for the endpoint
A[u][v] -= 1.0 / deg[u];
}
}
// Special boundary: The equation for endpoint n is fixed as 1 * f[n] = 0
A[n][n] = 1.0;
A[n][n + 1] = 0.0;
if (gaussian_elimination(n)) {
// Output the expected number of steps from starting point 1 to endpoint n
std::cout << std::fixed << std::setprecision(6) << ans[1] << "\n";
} else {
std::cout << "INF\n";
}
}
return 0;
}NOIP Practical Pitfall Guide
- Mixing the endpoint's row equation with other ordinary rows during elimination
The expected cost from endpoint $n$ to itself is clearly $0$. When constructing the matrix, it is absolutely forbidden to perform transition updates like
A[n][v] -= 1.0/deg[n]on the endpoint as if it were a regular node. Allowing the endpoint to update its successors is equivalent to permitting the process to "come back to life" after reaching the endpoint, which completely undermines the definition of expectation and leads to meaningless random numbers as results. - Floating-point precision failure due to neglecting pivot selection
Some participants, in an effort to simplify, omit the step of "finding the row with the maximum absolute value and swapping it" (i.e., not performing pivoting) during elimination. This might pass in benchmark tests, but under the tricky data conditions of NOIP, if a row's
A[r][r]is close to $10^{-14}$, directly using it as a divisor to eliminate other rows will amplify small floating-point errors to the level of $10^{14}$, causing the precision of the entire matrix to collapse instantaneously.
Classic NOIP/Luogu Problems
1. Luogu P3232 [HNOI2013] Random Walk
- Problem Description: Given an undirected connected graph, starting from node $1$, perform a random walk, stopping when reaching node $n$. Each step will randomly choose one edge with equal probability to walk through. Now you can renumber each edge in the graph from $1$ to $m$ (i.e., reassign edge weights) to minimize the expected total weight of the edges traversed during the walk.
- Essence of the Problem: Matrix solving for expected node visits and greedy weighting.
- Core Solution Idea: Based on the linear property of expectation, the total expected edge weight equals $\sum (\text{expected visits to edges} \times \text{edge weight})$. Hence, the core is to determine the expected visit count for each edge. The expected visit count for an edge $(u,v)$ essentially equals the expected count starting from $u$ multiplied by $ rac{1}{deg[u]}$ plus the expected count starting from $v$ multiplied by $ rac{1}{deg[v]}$. Thus, the problem translates to finding the expected visit count for each node $f[i]$. Using adjacency relationships, we can establish the equation:
$$f[i] = \sum_{(j,i) \in E, j \neq n} \frac{f[j]}{deg[j]} + [i == 1]$$
After solving for all $f[i]$ using Gaussian elimination, we can backtrack to derive the expected visit count for each edge. Finally, using a greedy strategy: assign smaller numbers to edges with higher expected visit counts, and the product sum will yield the minimum expectation.
2. Luogu P2973 [USACO10HOL] Bombing Travel
- Problem Description: A bomb is detonated at node $1$, with probability $P$ of exploding in place and probability $1-P$ of randomly choosing one edge to move to an adjacent node. Determine the absolute probability of the bomb exploding at each node.
- Essence of the Problem: Probability matrix convergence for non-terminal states via Gaussian elimination.
- Core Solution Idea: This problem does not involve expected backtracking but is purely about forward convergence of probabilities. Let $f[i]$ denote the expected count of the bomb reaching node $i$. Since there is a probability $P$ of exploding at each node, the actual probability of the bomb exploding at node $i$ is $f[i] \cdot P$. By establishing equations based on contributions from predecessor nodes:
$$f[i] = (1 - P) \sum_{(j,i) \in E} \frac{f[j]}{deg[j]} + [i == 1]$$
After constructing the augmented matrix of $n$ equations, we can directly apply Gaussian elimination, and the resulting $f[i] \times P$ will give the final explosion probability at each node.