《算法竞赛进阶指南》0x35高斯消元与线性空间 装备购买

题目链接：https://www.acwing.com/problem/content/211/

求矩阵的最大无关组的维数，也就是行向量的极大无关组，线性空间的一组基（因为线性空间的一组基可以表示线性空间中的其他任意的向量，他们之间不能相互表示），可以用高斯消元的方式，求维数，但是本题不仅仅要求得出维数，还得得出在这样的维数的情况下最小的花费，所以需要利用贪心的方法，扫描到第i个变量时，需要检查所有的含这个变量的最小的花费，可以证明，在不选这个花费的情况下情况不会变的更优（反证法证明）。中间可能会出现一些自由元，所以我们需要记录当前的非自由元构成的dimention。

还有一个问题就是，需要使用long double 防止除法溢出，longdouble大约支持1.2*10^-400~1.2*10^400之间的小数。这是一个重点。

代码：

#include<iostream>
#include<cstdio>
#include<math.h>
using namespace std;
#define maxn 510
const double eps=1e-8;
long double a[maxn][maxn];
int c[maxn];
int n,m;
int main(){
    double tmp;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%lf",&tmp);
            a[i][j]=tmp;
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        scanf("%lf",&tmp);
        c[i]=tmp;
    }
    
    int dim=0;//表示矩阵的维数 
    //对每个未知量进行一次消元，所以i的范围是到m 
    for(int i=1;i<=m;i++){
        int now=-1;
        for(int j=dim+1;j<=n;j++){//找出当前位置的最小的花费 
            if(fabs(a[j][i])>eps && (now==-1 || c[j]<c[now])){
                now=j;
            }
        }
        if(now==-1)continue;//当前主元是自由元
        dim++;//n个行向量对应的特征空间的维数增加
        ans+=c[now];
        
        for(int j=1;j<=m;j++)
            swap(a[now][j],a[dim][j]);
        swap(c[now],c[dim]);
        for(int j=1;j<=n;j++){//扫描所有除了当前行之外的行 
            if(j!=dim && fabs(a[j][i])>eps){
                long double rate=a[j][i]/a[dim][i];
                for(int k=i;k<=m;k++)
                    a[j][k]-=a[dim][k]*rate;//第j行减去第dim行的rate倍 
            }
        }         
    }
    cout<<dim<<" "<<ans<<endl; 
}