题解 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); } ```