AcWing 209. 装备购买
原题链接
困难
作者:
长夜未央
,
2022-07-30 09:50:57
,
所有人可见
,
阅读 187
#include<bits/stdc++.h>
#define maxn 100005
#define mod 1000000007
#define eps 1e-8
using namespace std;
typedef long long ll;
ll n,m;
long double a[505][505];
long double c[505];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
double temp;
cin>>temp;
a[i][j]=temp;
}
}
for(int i=1;i<=n;i++){
double temp;
cin>>temp;
c[i]=temp;
}
double sum=0;
ll num=0;
for(int i=1;i<=n;i++){
int flag=0;
for(int j=i;j<=n;j++){
if(fabs(a[j][i])>eps){
if(flag==0||c[j]<c[flag])
{
flag=j;
}
}
}
/*if(fabs(a[i][i])<eps){
num=i-1;
break;
}*/
if(flag==0) continue;
num++;
for(int k=1;k<=m;k++){
swap(a[i][k],a[flag][k]);
}
swap(c[i],c[flag]);
sum+=c[i];
for(int j=1;j<=n;j++){
if(i==j||fabs(a[j][i])<eps) continue;
long double state=a[j][i]/a[i][i];
for(int k=1;k<=m;k++){
a[j][k]-=a[i][k]*state;
}
}
}
cout<<num<<" "<<sum;
}