线性基，这题就是求秩

高斯消元，非零行向量的个数就是秩

最小代价只需在消元的时候选择代价小的即可

要开long double

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;int n,m,c[510];long double qg[510][510],qc[510];void guess(){ int d=1,mmin=0; for(int j=1;j<=m;j++) { int p=-1; for(int i=d;i<=n;i++) if(fabs(qg[i][j])>1e-8&&(p==-1||c[p]>c[i])) p=i; if(p==-1)continue; mmin+=c[p]; for(int k=j;k<=m;k++)swap(qg[p][k],qg[d][k]); swap(qc[p],qc[d]); swap(c[p],c[d]); for(int i=1;i<=n;i++) { if(i==d)continue; long double rate=qg[i][j]/qg[d][j]; for(int k=j;k<=m;k++)qg[i][k]-=qg[d][k]*rate; qc[i]-=qc[d]*rate; } d++; } printf("%d %d\n",d-1,mmin);}int main(){ freopen("1.in","r",stdin); freopen("1.out","w",stdout); scanf("%d%d",&n,&m); memset(qc,0,sizeof(qc)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%Lf",&qg[i][j]); for(int i=1;i<=n;i++)scanf("%d",&c[i]); guess(); return 0;}