P3265 [JLOI2015]装备购买

题目描述：

给N个整数向量，每个向量带权值，求权值和最小的线性基

题解：

按权值v从小->大排序，依次插入线性基。整数线性基的思想类似，只是此时“消去”不能直接xor完成，需要类似高斯消元一样for一遍

代码：

#include<bits/stdc++.h>
#define eps 1e-5
using namespace std;
struct node{
    double a[510];
    int w;
    bool operator <(const node x) const{
        return w<x.w;
    }
};
node q[510];
int p[510],n,m,ans,cnt;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%lfd",&q[i].a[j]);

    for(int i=1;i<=n;i++) scanf("%d",&q[i].w);

    sort(q+1,q+n+1);

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {

            if(abs(q[i].a[j])<=eps) continue;

            if(!p[j])
            {
                p[j]=i;
                cnt++;
                ans+=q[i].w;
                break;
            }
            else
            {
                double div=q[i].a[j]/q[p[j]].a[j];

                for(int k=j;k<=m;k++)
                {
                    q[i].a[k]-=div*q[p[j]].a[k];
                }
            }
        }
    }
    printf("%d %d",cnt,ans);
}