BZOJ 4004 [JLOI2015]装备购买

题目大意

给你N个向量，求出一个最大权值的线性无关组。

直接高斯消元，用long double解决实数问题。

#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long double ld;
const ld eps=1e-6;
int n,m,cnt,ans;
bool use[510];
struct gear{ld v[510];int c;}a[510];
bool cmp(const gear &x,const gear &y){return x.c<y.c;}
void gauss()
{
	int i,j,k,t;ld tmp;
	for(i=1;i<=m;++i)
	{
		for(t=1;t<=n;++t)
			if(!use[t]&&fabs(a[t].v[i])>eps)
				break;
		if(t>n) continue;
		cnt++,ans+=a[t].c,use[t]=true;
		for(j=1;j<=n;++j)
			if(!use[j])
				for(tmp=a[j].v[i]/a[t].v[i],k=i;k<=m;++k)
					a[j].v[k]-=tmp*a[t].v[k];
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	int i,j;
	for(i=1;i<=n;++i) for(j=1;j<=m;++j) scanf("%Lf",&a[i].v[j]);
	for(i=1;i<=n;++i) scanf("%d",&a[i].c);
	sort(a+1,a+n+1,cmp);
	gauss();
	printf("%d %d\n",cnt,ans);
	return 0;
}