「Bzoj 4004」「JLOI2015」装备购买 (高斯消元 + 线性基)

BZOJ 4004
题意：给你$n$个$m$维向量，每个向量有一个权值，求最小权极大线性无关组。

直接将其看作一个矩阵高斯消元，然后解出来的简化阶梯矩阵所有非零向量线性无关，称为秩。

对答案统计直接在消元过程中统计。

这题也让我知道高斯消元最后矩阵如果有一行有多个元素大于$0$意思是因为其他元没消掉这一位的数，并不是无解。

注意本题卡精度，可以开 long double

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int INF = 1000000000;
    const db eps = 1e-8;

    int n, m, c[505];
    db a[505][505];

    void clean() {
    }
    int solve() {

        clean();

        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            scanf("%Lf", &a[i][j]);

        for (int i = 1; i <= n; ++i) scanf("%d", &c[i]);

        int dim = 0, ans = 0;
        for (int i = 1; i <= min(m, n); ++i) {
            int mind = INF;
            for (int j = i; j <= n; ++j) 
                if (fabs(a[j][i]) > eps && mind > c[j]) 
                    swap(a[i], a[j]), mind = c[j], swap(c[i], c[j]);
            if (fabs(a[i][i]) < eps) continue ;
            ++dim, ans += c[i]; // 新增一个基底
            for (int j = 1; j <= n; ++j) if (i != j) {
                db rate = a[j][i] / a[i][i];
                for (int k = 1; k <= m; ++k) a[j][k] -= a[i][k] * rate;
            }
        }

        printf("%d %d\n", dim, ans);

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}