Template -「高斯消元」

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

double Abs(double x) { return x < 0 ? -x : x; }

double Max(double x, double y) { return x > y ? x : y; }

double Min(double x, double y) { return x < y ? x : y; }

int read() {

    int x = 0, k = 1;

    char s = getchar();

    while (s < '0' || s > '9') {

        if (s == '-')

            k = -1;

        s = getchar();

    }

    while ('0' <= s && s <= '9') {

        x = (x << 3) + (x << 1) + (s ^ 48);

        s = getchar();

    }

    return x * k;

}

void write(int x) {

    if (x < 0) {

        putchar('-');

        x = -x;

    }

    if (x > 9)

        write(x / 10);

    putchar(x % 10 + '0');

}

void print(int x, char c) {

    write(x);

    putchar(c);

}

const int MAXN = 5e2 + 5;

const int MAXM = 3e5 + 5;

struct Elimination {

    bool free[MAXN];

    int n, m, rk, opt;

    double a[MAXN][MAXN], x[MAXN], eps;

    Elimination() { eps = 1e-12; }

    Elimination(int N, int M) {

        n = N;

        m = M;

    }

    double Abs(double x) { return x < eps ? -x : x; }

    void Swap(double &x, double &y) {

        double t = x;

        x = y;

        y = t;

    }

    void clear() {

        for (int i = 1; i <= n; i++)

            for (int j = 1; j <= m; j++) a[i][j] = 0;

    }

    void calc() {

        int r = 1, c = 1;

        for (; r <= n && c <= m; r++, c++) {

            int pos = r;

            for (int i = r + 1; i <= n; i++)

                if (Abs(a[i][c]) > Abs(a[pos][c]))

                    pos = i;

            if (Abs(a[pos][c]) < eps) {

                r--;

                continue;

            }

            if (pos != r)

                for (int i = c; i <= m; i++) Swap(a[r][i], a[pos][i]);

            double t;

            for (int i = 1; i <= n; i++)

                if (i != r && Abs(a[i][c]) > eps) {

                    t = a[i][c] / a[r][c];

                    for (int j = m; j >= c; j--) a[i][j] -= t * a[r][j];

                }

        }

        rk = r;

    }

    void check() {

        opt = 1;

        for (int i = 1; i <= n; i++)

            if (Abs(a[i][i]) < eps && Abs(a[i][m]) > eps) {

                opt = -1;

                return;

            }

        for (int i = 1; i <= n; i++)

            if (Abs(a[i][i]) < eps && Abs(a[i][m]) < eps) {

                free[i] = true;

                opt = 0;

            } else

                x[i] = a[i][m] / a[i][i];

    }

};
巴特西

Template -「高斯消元」

最新文章

热门文章
