自动搬运

查看原文

来自洛谷，原作者为

	荣一鸣 **

搬运于2025-08-24 21:47:08，当前版本为作者最后更新于2018-08-09 15:15:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我们遇见的普通线性基（如模板题），都是在有关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);
}