WIKI

高斯消元

前置知识：线性方程组的初等变换

1. 交换某两行的位置
2. 用一个非0 的常数 $k$ 乘以某个方程
3. 把某行 乘以 $k$ 然后加到另一行上

线性方程组的解 有三种情况

1.有唯一解

形如
$$ \left[ \begin{array}{cccc|c} 1 & 0 & \ldots&0 & x_{1} \\ 0 & 1 & \ldots & 0 &x_{2}\\ \vdots & \vdots & \ddots & \vdots&\vdots \\ 0 & 0 & \ldots & 1 &x_{n} \end{array} \right] $$

2.有无穷多解

形如 出现 全0 行 ，代表 此行无效
$$ \left[ \begin{array}{cccc|c} 1 & 0 & \ldots&0 & x_{1} \\ 0 & 1 & \ldots & 0 &x_{2}\\ \vdots & \vdots & \ddots & \vdots&\vdots \\ 0 & 0 & \ldots & 0&0 \end{array} \right] $$

3.无解

形如 出现 矛盾行 ，代表方程组 无解
$$ \left[ \begin{array}{cccc|c} 1 & 0 & \ldots&0 & x_{1} \\ 0 & 1 & \ldots & 0 &x_{2}\\ \vdots & \vdots & \ddots & \vdots&\vdots \\ 0 & 0 & \ldots & 0&1 \end{array} \right] $$

高斯-约当消元方法

1. 从第一列开始选择一个非0 的系数所在的行(可以选最大的系数，避免 转换时 产生过大的数值)
   将这一行移动到第一行，此时 $x_1$ 是主元
2. 将$x_1$的 系数转换成 1
3. 利用 主元 $x_1$ 的系数，将其他行 这一列的 主元消去
4. 重复直到 只有对角线上 存在 主元 ，且系数都为 1

时间复杂度$O(n^3)$

code

#include <bits/stdc++.h>
using namespace std;
#define all(a) begin(a), end(a)
#define int long long
int n, m;
using ld = long double;
constexpr ld eps = 1E-6;
void solve() {
  cin >> n;
  vector<vector<ld>> a(n, vector<ld>(n + 1));
  for (auto &i : a)
    for (auto &j : i) cin >> j;
  for (int i = 0; i < n; i++) {
    int max = i;
    for (int j = i + 1; j < n; j++)
      if (fabs(a[j][i]) > fabs(a[max][i])) max = j;
    for (int j = 0; j <= n; j++) swap(a[i][j], a[max][j]);
    if (fabs(a[i][i]) < eps) return (void)(cout << "No Solution\n");
    for (int j = n; ~j; j--) a[i][j] = a[i][j] / a[i][i];
    for (int j = 0; j < n; j++) {
      if (j != i) {
        ld tmp = a[j][i];
        for (int k = 0; k <= n; k++) a[j][k] -= a[i][k] * tmp;
      }
    }
  }
  for (int i = 0; i < n; i++) cout << a[i][n] << "\n";
}

signed main() {
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(2);
  cin.tie(0), cout.tie(0);
  solve();
  return 0;
}