好吧刚开始不知道自己在写什么，，，后来写了线性方程组，又过了一天一上午终于明白了。。。
当然题意很显然：求代价最小的极大线性无关组。
那就高斯消元（好吧刚开始我不会用它来解这道题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\n",cnt,ans); }
然后不知自己刚开始哪里写锅了。。。那就先锅着。。。
原文：https://www.cnblogs.com/Jackpei/p/10861633.html