G68 实数线性基+高斯消元法 P3265 [JLOI2015] 装备购买

视频链接：G68 实数线性基+高斯消元法 P3265 [JLOI2015] 装备购买_哔哩哔哩_bilibili

P3265 [JLOI2015] 装备购买 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

// 线性基+高斯消元法 O(n*m*m)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const double eps=1e-5;
const int N=510;
int n,m;
struct node{
  double z[N]; //属性
  int c;       //花费
  bool operator<(node& b){
    return c<b.c;
  }
}a[N];
int p[N],cnt,ans;

void gauss(){ //高斯消元法
  for(int i=1;i<=n;++i){
    for(int j=1;j<=m;++j){
      if(abs(a[i].z[j])>eps){ //如果(i,j)>0
        if(!p[j]){ //如果p[j]不存在
          p[j]=i;  //记录最高位为第j位的线性基
          ans+=a[i].c; //累计花费
          cnt++;       //累计个数
          break;
        }
        else{ //如果p[j]存在，则行消元
          double d=a[i].z[j]/a[p[j]].z[j];
          for(int k=j;k<=m;++k)
            a[i].z[k]-=a[p[j]].z[k]*d;
        }
      }
    }
  }
}
int main(){
  cin>>n>>m;
  for(int i=1;i<=n;++i)
    for(int j=1;j<=m;++j) cin>>a[i].z[j];
  for(int i=1;i<=n;++i) cin>>a[i].c;
  sort(a+1,a+1+n); //按花费升序
  gauss();
  cout<<cnt<<' '<<ans<<endl;
}

// 线性基+贪心法 O(n*m*m)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const double eps=1e-5;
const int N=510;
int n,m;
struct node{
  double z[N]; //属性
  int c;       //花费
  bool operator<(node& b){
    return c<b.c;
  }
}a[N];
int p[N],cnt,ans;

void insert(int i){ //贪心法
  for(int j=1;j<=m;++j){
    if(abs(a[i].z[j])>eps){ //如果(i,j)>0
      if(!p[j]){ //如果p[j]不存在
        p[j]=i;  //记录最高位为第j位的线性基
        ans+=a[i].c; //累计花费
        cnt++;       //累计个数
        break;
      }
      else{ //如果p[j]存在，则行消元
        double d=a[i].z[j]/a[p[j]].z[j];
        for(int k=j;k<=m;++k)
          a[i].z[k]-=a[p[j]].z[k]*d;
      }
    }
  }
}
int main(){
  cin>>n>>m;
  for(int i=1;i<=n;++i)
    for(int j=1;j<=m;++j) cin>>a[i].z[j];
  for(int i=1;i<=n;++i) cin>>a[i].c;
  sort(a+1,a+1+n); //按花费升序
  for(int i=1;i<=n;++i) insert(i);
  cout<<cnt<<' '<<ans<<endl;
}