[SDOI2006] 线性方程组

核心判定逻辑

在高斯-若尔当消元（Gauss-Jordan Elimination）过程中，我们会尝试把矩阵化为简化行阶梯形矩阵。

秩（Rank）的概念：我们可以维护一个变量 r（当前有效行数/秩）。每当我们成功找到一个主元并进行消元后，r 加 1。消元结束后，如果 r <= n（即 r 没有指到第 n+1 行），说明矩阵的秩小于未知数的个数，此时不是唯一解。
无解（No Solution）的条件： “0 = 非0”。当消元结束后，如果存在某一行 $i$ （ $i \ge r$ ），其左边所有系数系数 $a_{i,1} \dots a_{i,n}$ 全部为 0，但右边的常数项 $b_i$ （即 $a_{i, n+1}$ ）不为 0。这意味着出现了 $0 \cdot x_1 + \dots + 0 \cdot x_n = k \quad (k \neq 0)$ 的矛盾方程。 优先级： 无解的判定优先级高于无穷多解。只要发现矛盾，立即判无解。
无穷多解（Infinite Solutions）的条件： “0 = 0” 且无矛盾。如果消元结束后，r <= n（秩不满），并且我们检查了所有剩余的空行，发现它们的常数项也全都是 0（即 $0=0$ ）。这意味着有自由变量（Free Variables），方程组有无穷多解。

代码实现

cpp

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>

using namespace std;

const int MAXN = 55;
const double EPS = 1e-7;

int n;
double a[MAXN][MAXN];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n + 1; j++) {
            cin >> a[i][j];
        }
    }

    // r: 当前正在处理的行 (rank)
    // c: 当前正在处理的列
    int r = 1; 
    for (int c = 1; c <= n && r <= n; c++) {
        // 1. 找主元：在当前列 c 中，寻找从第 r 行开始绝对值最大的行
        int max_r = r;
        for (int i = r + 1; i <= n; i++) {
            if (fabs(a[i][c]) > fabs(a[max_r][c])) {
                max_r = i;
            }
        }

        // 2. 关键判断：如果这一列最大值已经是0了，说明这一列无法作为主元
        // 这意味着 x_c 是一个自由变量，或者这一列与前面的列线性相关
        if (fabs(a[max_r][c]) < EPS) {
            continue; // 重点：r 不增加，直接处理下一列
        }

        // 3. 交换行
        for (int j = 1; j <= n + 1; j++) swap(a[r][j], a[max_r][j]);

        // 4. 消元 (Gauss-Jordan)
        // 这里的处理稍微不同，我们不急着把 a[r][c] 归一化为 1
        // 而是直接用 a[r][c] 去消其他行，这样可以减少精度误差
        for (int i = 1; i <= n; i++) {
            if (i == r) continue;
            double ratio = a[i][c] / a[r][c];
            for (int j = c; j <= n + 1; j++) { // 从 c 开始即可，前面的已经是0了
                a[i][j] -= ratio * a[r][j];
            }
        }

        r++; // 成功消元一次，有效行数+1
    }

    // 此时 r 指向的是“下一个要填充的行”。
    // 如果 r > n，说明找到了 n 个主元，满秩，唯一解。
    // 如果 r <= n，说明秩不满。

    if (r <= n) {
        // 先判断是否无解：检查剩下的行是否出现 "0 = 非0"
        for (int i = r; i <= n; i++) {
            if (fabs(a[i][n + 1]) > EPS) {
                cout << -1 << endl; // 无解
                return 0;
            }
        }
        // 如果没有矛盾，那就是无穷解
        cout << 0 << endl; 
    } else {
        // 唯一解
        // 此时矩阵已经化为对角矩阵 (实际上是每行只有一个非零系数，但不一定是1)
        // a[i][i] * x_i = a[i][n+1]
        for (int i = 1; i <= n; i++) {
            // 注意：因为上面循环里 r 和 c 是分离的，如果是唯一解，
            // 最终矩阵的第 i 行的主元一定在第 i 列。
            double ans = a[i][n + 1] / a[i][i];
            
            // 修正 -0.00 的情况
            if (fabs(ans) < EPS) ans = 0.0; 
            
            printf("x%d=%.2lf\n", i, ans);
        }
    }

    return 0;
}

详细图解：为什么代码要这样写？

1. 唯一解的情况

矩阵最终会变成标准的对角线形式：

\begin{bmatrix} k_1 & 0 & 0 & | & b_1 \\ 0 & k_2 & 0 & | & b_2 \\ 0 & 0 & k_3 & | & b_3 \end{bmatrix}

此时 r 会一直加到 n+1，程序进入 else 分支，直接计算 $x_i = b_i / k_i$ 。

2. “0” 导致的主元跳过（Rank < N）

假设有方程组：

\begin{cases} x + y + z = 3 \\ x + y + z = 4 \end{cases}

这显然无解。当处理第一列（ $x$ ）时，Row 1 变成主元，消掉 Row 2 的 $x$ 。 Row 2 变成了 $0 \cdot x + 0 \cdot y + 0 \cdot z = 1$ 。此时代码执行逻辑：

c=1 (x列): 找到主元，r 变成 2。
c=2 (y列): Row 2 的 $y$ 系数是 0。最大值是 0。continue。r 还是 2。
c=3 (z列): Row 2 的 $z$ 系数是 0。最大值是 0。continue。r 还是 2。

循环结束，r = 2，r <= n。

3. 判定无解 vs 无穷解

接着上面的例子，r=2。我们检查从 row 2 到 n 的行。 Row 2 的状态是 [0, 0, 0 | 1]。代码检测 a[2][n+1] (即 1) > EPS。判定为：无解 (-1)。

如果 Row 2 的状态是 [0, 0, 0 | 0]（比如原方程是两个完全一样的式子），那么循环里检测不到非 0 的右边值。判定为：无穷解 (0)。

总结差异点

P3389 (简单版): 假设一定有解，所以不需要 continue 跳过列，也不需要检查 r <= n。
P2455 (进阶版):
1. 列与行分离：for (c...) 内部维护 r。如果当前列全是 0，跳过该列，r 不动。
2. 后置检查：消元完成后，先查 rank 是否满。不满则检查是否存在“左 0 右非 0”的矛盾行。