题解 P3265 【[JLOI2015]装备购买】

· · 题解

我们遇见的普通线性基（如模板题），都是在有关2进制与其异或和上用的

而这里用的是实数的线性基，在学实数的线性基之前，必须知道高斯消元的原理（因为我学线性基的时候没学高斯消元！！！）

那么我先讲一下为什么用高斯消元。

我们可以看到，如果物品aj可以用a1....aj-1组合而出的话，我们可以通过公式得到

k1*a1.x1+k2*a2.x1+k3*a3.x1+...+kj-1*aj-1.x1=aj.x1
k1*a1.x2+k2*a2.x2+k3*a3.x2+...+kj-1*aj-1.x2=aj.x2
......
k1*a1.xm+k2*a2.xm+k3.a3.xm+...+kj-1*aj-1.xm=aj.xm

我们就是要求出是否有这样的一组k使得上述等式成立

至于求解，我们可以用高斯消元。

但是由于这样做太过于麻烦，所以我们要结合线性基

假如我们将每个物品的属性看作向量，那么，我们要求的就是其中的一组基（如果一个物品可以通过其他的物品组合而成，那么它就不能是基的一部分）

我们上面的等式转化一下变成下面的

a1.x1,a1.x2,a1.x3...a1.xm ........1
a2.x1,a2.x2,a2.x3...a2.xm ........2
a3.x1,a3.x2,a3.x3...a3.xm ........3
...
aj.x1,aj.x2,aj.x3...aj.xm ........4

我们如果用高斯消元，用第一行的x1消去下面所有行的x1

然后用第二行剩下的x2（如果x2没有的话可以换一下行）,然后把剩下的行的x2消去

.....

如果消到最后，剩下的j所有项为0，那么aj就可以不选了。

多么愉快的是用高斯消元就行了！

这里就不讲高斯消元了

如果在消过元后有一个位置不是0，那么它就可以作为第i位的基（可以这么说吗？）

剩下的就是贪心了

下面就是代码，结合上面理解一下

#include<bits/stdc++.h>
#define cmp 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(q[i].a[j]<=cmp&&q[i].a[j]>=-cmp) continue;
            if(!p[j]){
                p[j]=i;
                cnt++;ans+=q[i].w;
                break;
            }
            else{
                double alpha=q[i].a[j]/q[p[j]].a[j];
                for(int k=j;k<=m;k++){
                    q[i].a[k]-=alpha*q[p[j]].a[k];
                }
            }
        }
    }
    printf("%d %d",cnt,ans);
}