贪心+高斯消元线性基--[JLOI2015]装备购买

本文主要是介绍贪心+高斯消元线性基--[JLOI2015]装备购买，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

bzoj4004
luogu3265

题目大意：
n 件装备每件装备有m 件属性以及价格ci，属性可以用向量zi 表示，
现在想要购买尽量多的装备使得装备的属性向量线性无关，求最小代价

solution：
属性要求满足拟阵条件
贪心维护一个线性基即可
O(n^2*m)

拟阵这东西比较复杂···我们只需要知道它是满足贪心的就行了
线性基这东西也比较复杂···其实根本用不着，就是个线性表出，普通gauss就行
贪心的按照代价从小到大排序
然后枚举，枚举到i，如果i的所有属性都被消成0
则i可以被其他向量表出，否则将其加到答案里
然后把后面的都消掉

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define maxn 505
using namespace std;
int n,m,cnt,ans;
const double eps=1e-6;struct qwqwq{int c; long double a[maxn];//居然要用long double??????
}eq[maxn];inline int rd(){int x=0,f=1;char c=' ';while(c<'0' || c>'9') {if(c=='-')f=-1;c=getchar();}while(c<='9' && c>='0') x=x*10+c-'0',c=getchar();return x*f;
}
bool cmp(qwqwq x,qwqwq y) {return x.c<y.c;}void Gauss(){for(int i=1;i<=n;i++){bool flg=false;for(int j=i;j<=m;j++) if(fabs(eq[i].a[j])>eps) {flg=true;break;}if(!flg) continue;cnt++; ans+=eq[i].c;for(int j=i+1;j<=n;j++){long double rate=eq[j].a[i]/eq[i].a[i];for(int k=i;k<=m;k++) eq[j].a[k]-=rate*eq[i].a[k];}}
}int main(){n=rd(); m=rd();for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) eq[i].a[j]=rd();for(int i=1;i<=n;i++) eq[i].c=rd();sort(eq+1,eq+n+1,cmp);Gauss();printf("%d %d\n",cnt,ans);//输出格式不对wa了一次···return 0;
}

这篇关于贪心+高斯消元线性基--[JLOI2015]装备购买的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---