高斯消元

高斯消元解线性方程组

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

https://www.luogu.com.cn/problem/P3389

题意：给定一个线性方程组，对其求解。

#include <bits/stdc++.h>
using namespace std;

const char nl = '
';
const int N = 100 + 50;
const double eps = 1e-6;

int n;
double a[N][N];

int gauss(){
    int c, r;
    for (c = 0, r = 0; c < n; ++c){
        int t = r;
        for (int i = r; i < n; ++i)
            if (fabs(a[i][c]) > fabs(a[t][c])) t = i;

        if (fabs(a[t][c]) < eps) continue;

        for (int i = c; i <= n; ++i) swap(a[r][i], a[t][i]);
        for (int i = n; i >= c; --i) a[r][i] /= a[r][c];
        for (int i = r + 1; i < n; ++i)
            if (fabs(a[i][c]) > eps)
                for (int j = n; j >= c; --j)
                    a[i][j] -= a[i][c] * a[r][j];

        ++r;
    }

    if (r < n){
        for (int i = r; i < n; ++i)
            if (fabs(a[i][n]) > eps) return 2;  //无解
        return 1;   //有无穷多组解
    }

    for (int i = n - 1; i >= 0; --i)
        for (int j = i + 1; j < n; ++j)
            a[i][n] -= a[i][j] * a[j][n];

    return 0;   //有唯一解
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cout << fixed << setprecision(2);

    cin >> n;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j <= n; ++j) cin >> a[i][j];

    int t = gauss();
    if (t == 0)
        for (int i = 0; i < n; ++i) cout << a[i][n] << nl;
    else
        cout << "No Solution" << nl;

    return 0;
}