bzoj4004: [JLOI2015]装备购买

线性基，这题就是求秩

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

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

要开long double

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
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
",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;
}

bzoj4004: [JLOI2015]装备购买

相关推荐