求最小权极大线性无关组.
先将所有向量按权值排序, 从小到大依次判断, 若能被前面已选向量线性表出则不选, 这样一定最优.
据说是用拟阵来证明, 但感性理解一下感觉比较显然, 首先这样个数一定是最多的, 其次对于一个线性相关组, 没有被选上的一定是最大的那个向量, 于是解一定最优.
- #include<cmath>
- #include<cstdio>
- #include<algorithm>
- #define rep(i,l,r) for (int i=(l); i<=(r); i++)
- typedef long double ld;
- using namespace std;
- const int N=510;
- const ld eps=1e-6;
- int n,m,ans1,ans2;
- ld p[N][N];
- struct P{ ld p[N]; int v; }a[N];
- bool operator <(const P &a,const P &b){ return a.v<b.v; }
- int main(){
- freopen("bzoj4004.in","r",stdin);
- freopen("bzoj4004.out","w",stdout);
- scanf("%d%d",&n,&m);
- rep(i,1,n) rep(j,1,m) scanf("%Lf",&a[i].p[j]);
- rep(i,1,n) scanf("%d",&a[i].v);
- sort(a+1,a+n+1);
- rep(k,1,n) rep(i,1,m){
- if (fabs(a[k].p[i])<eps) continue;
- if (fabs(p[i][i])<eps){
- rep(j,i,n) p[i][j]=a[k].p[j];
- ans1++; ans2+=a[k].v; break;
- }
- for (int j=m; j>=i; j--) a[k].p[j]-=p[i][j]*a[k].p[i]/p[i][i];
- }
- printf("%d %d\n",ans1,ans2);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2828093.html