Luogu P3265 [JLOI2015]装备购买

好吧刚开始不知道自己在写什么，，，后来写了线性方程组，又过了一天一上午终于明白了。。。

当然题意很显然：求代价最小的极大线性无关组。

那就高斯消元（好吧刚开始我不会用它来解这道题qwq）

第一个循环是枚举消哪个元，即i；然后去找有系数且代价最小的一行，特别地，如果所有行都没有系数，那么他就是自由元。。不计入答案；

然后就消就好了。。。

#include<cstdio>
#include<iostream>
#define R register int
using namespace std;
const int N=510;
const long double eps=1E-7;
long double a[N][N],c[N];
int n,m,k,cnt,ans;
inline bool ck0(double x) {return x<=eps&&x>=-eps;}
inline void Gauss() { 
    for(R i=1;i<=m;++i) { R pos=0;
        for(R j=cnt+1;j<=n;++j) if(!ck0(a[j][i])&&(pos==0||c[pos]>c[j])) pos=j;
        if(pos==0) continue; ++cnt,ans+=c[pos];
        if(pos!=cnt) swap(a[pos],a[cnt]),swap(c[pos],c[cnt]);
        for(R j=cnt+1;j<=n;++j) if(!ck0(a[j][i])) {
            register long double t=a[j][i]/a[cnt][i];
            for(R k=1;k<=m;++k) a[j][k]-=a[cnt][k]*t;
        }
    }
}
signed main() { 
    scanf("%d %d",&n,&m); for(R i=1;i<=n;++i) for(R j=1;j<=m;++j) scanf("%Lf",&a[i][j]);
    for(R i=1;i<=n;++i) scanf("%Lf",&c[i]);
    Gauss(); printf("%d %d
",cnt,ans);
}

然后不知自己刚开始哪里写锅了。。。那就先锅着。。。

2019.05.14