P3265 [JLOI2015]装备购买线性无关组

本文主要是介绍P3265 [JLOI2015]装备购买线性无关组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接：https://ac.nowcoder.com/acm/problem/20146
来源：牛客网

题目描述

脸哥最近在玩一款神奇的游戏，这个游戏里有 n 件装备，每件装备有 m 个属性，用向量zi(aj ,.....,am) 表示 (1 ≤ i ≤ n; 1 ≤ j ≤ m)，每个装备需要花费 ci，现在脸哥想买一些装备，但是脸哥很穷，所以总是盘算着怎样才能花尽量少的钱买尽量多的装备。

对于脸哥来说，如果一件装备的属性能用购买的其他装备组合出（也就是说脸哥可以利用手上的这些装备组合出这件装备的效果），那么这件装备就没有买的必要了。

严格的定义是，如果脸哥买了 zi1,.....zip这 p 件装备，那么对于任意待决定的 zh，不存在 b1,....,bp 使得 b1zi1 + ... + bpzip = zh（b 是实数），那么脸哥就会买 zh，否则 zh 对脸哥就是无用的了，自然不必购买。

举个例子,z1 =(1; 2; 3);z2 =(3; 4; 5);zh =(2; 3; 4)，b1 =1/2，b2 =1/2，就有 b1z1 + b2z2 = zh，那么如果脸哥买了 z1 和 z2 就不会再买 zh 了。脸哥想要在买下最多数量的装备的情况下花最少的钱，你能帮他算一下吗？

输入描述:

第一行两个数 n;m。

接下来 n 行，每行 m 个数，其中第 i 行描述装备 i 的各项属性值。

接下来一行 n 个数，其中 ci 表示购买第 i 件装备的花费。

输出描述:

一行两个数，第一个数表示能够购买的最多装备数量
第二个数表示在购买最多数量的装备的情况下的最小花费

示例1

输入

复制

输出

复制

2 2

我们遇见的普通线性基（如模板题），都是在有关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位的基（可以这么说吗？）

贪心。先按照价值从小到大排序

pos[j]代表着第 j 项的基底在第 i 个式子里面

如果我们找到了一个基底

我们就break掉

下个方程碰到这个基底，把他后面的所有的都模上（减去）含有基底的那个方程

也就是消元的思想

此外，这道题还可能卡精度（不过我没卡），可能要再模上一个大质数取逆元，在整数区域内求解

#include<bits/stdc++.h>
using namespace std;
struct node{
double val[555];
int cost;
};
bool cmp(const node &a,const node &b)
{return a.cost<b.cost;
}
node p[555];
int pos[555];
double eps=1e-5;
int main()
{int n,m;scanf("%d%d",&n,&m);for(int i=0;i<n;i++){for(int j=0;j<m;j++){scanf("%lf",&p[i].val[j]);}}for(int i=0;i<n;i++){scanf("%d",&p[i].cost);}sort(p,p+n,cmp);memset(pos,-1,sizeof(pos));int num=0,f=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(fabs(p[i].val[j])<=eps)continue;if(pos[j]==-1){pos[j]=i;num++;f+=p[i].cost;break;}else{double xs=p[i].val[j]/p[pos[j]].val[j];for(int k=j;k<m;k++){p[i].val[k]-=p[pos[j]].val[k]*xs;}}}}printf("%d %d\n",num,f);}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
ll val[555];
ll cost;
};
ll mod=1e9+7;
ll qpow(ll a,ll n)
{ll ans=1;while(n){if(n&1)ans=ans*a%mod;a=a*a%mod;n>>=1;}return ans;
}
bool cmp(const node &a,const node &b)
{return a.cost<b.cost;
}
node p[555];
ll pos[555];
double eps=1e-5;
int main()
{ll n,m;scanf("%lld%lld",&n,&m);for(ll i=0;i<n;i++){for(ll j=0;j<m;j++){scanf("%lld",&p[i].val[j]);}}for(ll i=0;i<n;i++){scanf("%lld",&p[i].cost);}sort(p,p+n,cmp);memset(pos,-1,sizeof(pos));ll num=0,f=0;for(ll i=0;i<n;i++){for(ll j=0;j<m;j++){if(fabs(p[i].val[j])<=eps)continue;if(pos[j]==-1){pos[j]=i;num++;f+=p[i].cost;break;}else{ll xs=p[i].val[j]*qpow(p[pos[j]].val[j],mod-2)%mod;for(ll k=j;k<m;k++){p[i].val[k]=(p[i].val[k]-p[pos[j]].val[k]*xs)%mod;}}}}printf("%lld %lld\n",num,f);}