求最小权极大线性无关组。
先将所有向量按权值排序，从小到大依次判断，若能被前面已选向量线性表出则不选，这样一定最优。
据说是用拟阵来证明，但感性理解一下感觉比较显然，首先这样个数一定是最多的，其次对于一个线性相关组，没有被选上的一定是最大的那个向量，于是解一定最优。
#include<cmath>
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef long double ld;
using namespace std; const int N=;
const ld eps=1e-;
int n,m,ans1,ans2;
ld p[N][N]; struct P{ ld p[N]; int v; }a[N];
bool operator <(const P &a,const P &b){ return a.v<b.v; } int main(){
freopen("bzoj4004.in","r",stdin);
freopen("bzoj4004.out","w",stdout);
scanf("%d%d",&n,&m);
rep(i,,n) rep(j,,m) scanf("%Lf",&a[i].p[j]);
rep(i,,n) scanf("%d",&a[i].v);
sort(a+,a+n+);
rep(k,,n) rep(i,,m){
if (fabs(a[k].p[i])<eps) continue;
if (fabs(p[i][i])<eps){
rep(j,i,n) p[i][j]=a[k].p[j];
ans1++; ans2+=a[k].v; break;
}
for (int j=m; j>=i; j--) a[k].p[j]-=p[i][j]*a[k].p[i]/p[i][i];
}
printf("%d %d\n",ans1,ans2);
return ;
}