# 题意
有n个装备，每个装备有m个属性，如果一个装备的所有属性可以由其他装备组合得到，那么就不会买这个装备，每个装备有一个价格，求最多能购买的装备数量和最少花的钱
# 题解
将n个装备看成n个维度为m的向量，题意所说的一个装备的所有属性可以由其他装备组合得到，那么就不会买这个装备所以买的都是不能由其他装备组合得到的，
所以求得就是能由这n个向量表出的线性空间的基，进行高斯消元即可，同时又要求最小花费，只要在高斯消元的过程中贪心选择价格最小的主元即可
1 #include <bits/stdc++.h> 2 #define eps 1e-8 3 using namespace std; 4 const int N=510; 5 int n,m; 6 int ans; 7 long double a[N][N],v[N];// 最后一列开始存的是方程右边常数，运算后解 8 int gauss() 9 { 10 int c, r; 11 for (c = 0, r = 0; c < m; c ++ ){ 12 int t = r; 13 for (int i = r; i < n; i ++ ) 14 if (fabs(a[i][c]) > eps && (t==r || v[i]<v[t]))//找到当前列最大的行 15 t = i; 16 if (fabs(a[t][c]) < eps) continue; 17 ans+=v[t]; 18 for (int i = c; i < m ; i ++ ) swap(a[t][i], a[r][i]); 19 swap(v[t],v[r]); 20 for (int i = m-1; i >= c; i -- ) a[r][i] /= a[r][c]; 21 for (int i = r + 1; i < n; i ++ )//后面行这一列变0 22 if (fabs(a[i][c]) > eps) 23 for (int j = m-1; j >= c; j -- ) 24 a[i][j] -= a[r][j] * a[i][c]; 25 r ++ ; 26 } 27 return r; 28 } 29 int main(){ 30 scanf("%d%d",&n,&m); 31 for(int i=0;i<n;i++) 32 for(int j=0;j<m;j++){ 33 double t; 34 scanf("%lf", &t); 35 a[i][j] = t; 36 } 37 for(int i=0;i<n;i++){ 38 double t; 39 scanf("%lf", &t); 40 v[i] = t; 41 } 42 int r=gauss(); 43 printf("%d %d ",r,ans); 44 }