rt,自己感觉挺对的,阳历也能过。。
难道这种枚举元逐个消掉的做法根本就是假的?
#include<bits/stdc++.h>
using namespace std;
using db=double;
const db eps=1e-7;
const bool equ(double d1,double d2){
return abs(d1-d2)<=eps;
}
const int N=505;
int n,m;db tmp;
struct mono{
int cst;
bool used=0;
vector<db>prop;
bool operator<(mono m1)const{
return cst<m1.cst;
}
}A[N];
int cnt,ans;
int main(){
//File(1,1);
cin>>n>>m;
for(int i=1;i<=n;i++)A[i].prop.push_back(-114514);
for(int i=1;i<=n;i++){
for(int i=1;i<=m;i++){cin>>tmp,A[i].prop.push_back(tmp);}
}
for(int i=1;i<=n;i++)cin>>A[i].cst;
sort(A+1,A+1+n);
for(int i=1;i<=m;i++){
int M=0;
for(int j=1;j<=n;j++){
if(!equ(A[j].prop[i],0.0) and !A[j].used){
M=j;
break;
}
}
if(!M)continue;
cnt++,ans+=A[M].cst,A[M].used=1;
for(int j=1;j<=n;j++){
if(equ(A[j].prop[i],0.0) or j==M)continue;
db rt=A[j].prop[i]/A[M].prop[i];
for(int k=1;k<=m;k++){
A[j].prop[k]-=A[M].prop[k]*rt;
}
}
}
printf("%d %d\n",cnt,ans);
}